比赛 |
20120717 |
评测结果 |
AAPPWWWWWW |
题目名称 |
信使问题b |
最终得分 |
30 |
用户昵称 |
了反取字名我擦 |
运行时间 |
0.785 s |
代码语言 |
C++ |
内存使用 |
5.81 MiB |
提交时间 |
2012-07-17 11:37:13 |
显示代码纯文本
#include<fstream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
ifstream fi("postmanb.in");
ofstream fo("postmanb.out");
int n;
double M=0,m=99999999;
struct point
{
int x;
int y;
}p[100001],res[100001];
int cmp(point p1,point p2)
{
return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
bool ra(point p1,point p2,point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)>(p3.x-p1.x)*(p2.y-p1.y);
}
int main()
{
fi>>n;
for(int i=0;i<n;i++)
fi>>p[i].x>>p[i].y;
sort(p,p+n,cmp);
res[0]=p[0];
res[1]=p[1];
int top=1;
for(int i=2;i<n;i++)
{
while(top&&!ra(res[top],res[top-1],p[i]))
top--;
res[++top]=p[i];
}
int len=top;
res[++top]=p[n-2];
for(int i=n-3;i>=0;i--)
{
while(top!=len&&!ra(res[top],res[top-1],p[i]))
top--;
res[++top]=p[i];
}
for(int i=0;i<top;i++)
for(int j=i+1;j<top;j++)
if(sqrt((double)((res[i].x-res[j].x)*(res[i].x-res[j].x)+(res[i].y-res[j].y)*(res[i].y-res[j].y)))>M)
M=sqrt((double)((res[i].x-res[j].x)*(res[i].x-res[j].x)+(res[i].y-res[j].y)*(res[i].y-res[j].y)));
fo<<M<<endl;
if(n<=10000)
{
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(sqrt((double)((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)))<m)
m=sqrt((double)((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)));
fo<<m;
}
fi.close();
fo.close();
return 0;
}