题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1185

枚举一条边,维护上、左、右方的点;

上方点到这条边距离最远,所以用叉积求面积维护;

左右点到这条边的射影最长(!),所以用点积求射影维护;

因为维护的点是只能逆时针走的,所以初始的左边点要特殊处理一下,其实等于右边点即可,然后可以走过去到合适位置;

然后维护矩形的四个端点,就是根据距离,从边的端点走过去,还挺有意思的;

注意不要输出 -0;

然而这其实是假的呵呵,Narh 一拍就出错了,还是很小的数据很明显的错囧

只是不知道哪里错,怎么调...

代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
db const eps=1e-;
int const xn=;
int n;
db ans;
int dmp(db x){if(fabs(x)<=eps)return ; return x>eps?:-;}
struct P{
db x,y;
P(db x=,db y=):x(x),y(y) {}
bool operator < (const P &b) const
{return dmp(x-b.x)<||dmp(x-b.x)==&&dmp(y-b.y)<;}
P operator + (const P &b) const
{return P(x+b.x,y+b.y);}
P operator - (const P &b) const
{return P(x-b.x,y-b.y);}
P operator * (const db &v) const
{return P(x*v,y*v);}
P operator / (const db &v) const
{return P(x/v,y/v);}
}p[xn],c[xn],pos[];
db cross(P a,P b){return a.x*b.y-a.y*b.x;}
db dot(P a,P b){return a.x*b.x+a.y*b.y;}
void find()
{
sort(p+,p+n+); int top=;
for(int i=;i<=n;i++)
{
while(top>&&dmp(cross(c[top]-c[top-],p[i]-c[top]))<=)top--;
c[++top]=p[i];
}
int num=top;
for(int i=n-;i;i--)
{
while(top>num&&dmp(cross(c[top]-c[top-],p[i]-c[top]))<=)top--;
c[++top]=p[i];
}
n=top-;
}
int upt(int x){if(x>n)x-=n; if(x<)x+=n; return x;}
db sqr(db x){return x*x;}
db dis(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
bool cmp(P a,P b){return dmp(a.y-b.y)<||(dmp(a.y-b.y)==&&dmp(a.x-b.x)<);}
void rc()
{
ans=-;
//int p=2,l=1,r=2;//
int p=,l=,r=; c[n+]=c[];
for(int i=;i<=n;i++)
{
db d=dis(c[i],c[i+]);
while(dmp(cross(c[i]-c[p],c[i+]-c[p])-cross(c[i]-c[p+],c[i+]-c[p+]))<=)p=upt(p+);
while(dmp(dot(c[r]-c[i],c[i+]-c[i])-dot(c[r+]-c[i],c[i+]-c[i]))<=)r=upt(r+);
if(i==)l=r;//
while(dmp(dot(c[l]-c[i],c[i+]-c[i])-dot(c[l+]-c[i],c[i+]-c[i]))>=)l=upt(l+);
db L=dot(c[i+]-c[i],c[l]-c[i])/d;
db R=dot(c[i+]-c[i],c[r]-c[i])/d;
db H=cross(c[i]-c[p],c[i+]-c[p])/d;
db tmp=(R-L)*H;
if(ans<||dmp(ans-tmp)>)
{
ans=tmp;
pos[]=c[i]+(c[i+]-c[i])*(R/d);
pos[]=pos[]+(c[r]-pos[])*(H/dis(c[r],pos[]));
//pos[2]=pos[1]+(c[p]-pos[1])*((R-L)/dis(c[p],pos[1]));//也可
pos[]=pos[]+(c[i]-pos[])*((R-L)/dis(c[i],pos[]));
pos[]=pos[]+(pos[]-pos[]);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
find();
rc();
printf("%.5f\n",ans);
int st=;
for(int i=;i<;i++)if(cmp(pos[i],pos[st]))st=i;
for(int i=st,cnt=;cnt<=;i=(i+)%,cnt++)
{
if(fabs(pos[i].x)<=eps)pos[i].x=;
if(fabs(pos[i].y)<=eps)pos[i].y=;
printf("%.5f %.5f\n",pos[i].x,pos[i].y);
}
return ;
}

最新文章

  1. AC日记——阶乘和 openjudge 1.6 15
  2. 为什么使用Sass
  3. linux增加根分区大小
  4. Oracle数据库字符集修改
  5. 总结源码编译安装mysql
  6. Say To ME
  7. Windows Server 2008防火墙问题及Sql Server2005用户登录问题
  8. POJ 1562 Oil Deposits
  9. 2014.3.12-C语言小测试
  10. c++内存优化:二级间接索引模式内存池
  11. Hibernate Mapping Exception:-9
  12. 基于HTML5的WebGL实现的2D3D迷宫小游戏
  13. Android Studio精彩案例(五)《JSMS短信验证码功能实现》
  14. Qt 快捷键
  15. with与上下文管理器
  16. 牛客网多校第3场C-shuffle card 平衡树或stl(rope)
  17. 用PowerDesigner建立概念模型的问题:不能创建相同字段名的关键字段
  18. 20155231 邵煜楠《网络对抗技术》实验一 PC平台逆向破解
  19. Selenium2+python自动化41-绕过验证码(add_cookie)
  20. 存储库之——MongoDB

热门文章

  1. 九度OJ 1260:珍珠项链 (字符串处理、DP)
  2. Virtualbox报错------> VirtualBox虚拟机下鼠标不正常的解决方法
  3. Netbeans8.0设置Consola字体并解决中文乱码问题
  4. Activiti使用过程_1
  5. Web Service概念辨析
  6. DOM指针
  7. CAS的实现Atomic类库
  8. HackerRank - flipping-the-matrix 【数学】
  9. 【leetcode刷题笔记】Longest Common Prefix
  10. debian下使用ft232为stm32f429i-discovery烧写uboot和uImage