比赛 |
20120717 |
评测结果 |
AAAATTTTTT |
题目名称 |
信使问题b |
最终得分 |
40 |
用户昵称 |
QhelDIV |
运行时间 |
3.221 s |
代码语言 |
C++ |
内存使用 |
13.74 MiB |
提交时间 |
2012-07-17 11:55:53 |
显示代码纯文本
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("postmanb.in");
ofstream fout("postmanb.out");
int i,N,pos,n;
class Node
{
public:
int x,y,pos;
}P[200000];
struct Point{
double x,y;
};
class Vector
{
public:
int x,y,pos;
}V[200000];
class S
{
public:
int list[200000],top,pos;
void push(int key)
{
list[++top]=key;
}
void pop()
{
top--;
}
}Stack;
bool cmpx(Point *p1,Point *p2)
{
return p1->x < p2->x;
}
bool cmpy(Point *p1,Point *p2)
{
return p1->y < p2->y;
}
int CP(Vector a,Vector b)
{
return a.x*b.y-a.y*b.x;
}
bool Cmp(Node a,Node b)
{
if(CP(V[a.pos],V[b.pos])<0 || a.pos==pos)
return true;
return false;
}
void Initialize()
{
int i,Ymin=~0u>>1,Xmin=~0u>>1;
fin>>N;
for(i=1;i<=N;i++)
{
fin>>P[i].x>>P[i].y;
if(P[i].y<Ymin || (P[i].y==Ymin && P[i].x<Xmin))
{
Ymin=P[i].x;
Xmin=P[i].y;
pos=i;
}
}
for(i=1;i<=N;i++)
{
V[i].x=P[i].x-P[pos].x,V[i].y=P[i].y-P[pos].y;
V[i].pos=i;P[i].pos=i;
}
sort(P+1,P+N+1,Cmp);
for(i=1;i<=N;i++)
P[i].pos=i;
}
void Graham_Scan()
{
Vector v,vv;
Stack.push(P[1].pos);
Stack.push(P[2].pos);
for(i=3;i<=N;i++)
{
Stack.list[++Stack.top]=i;
vv.x=P[Stack.list[Stack.top-1]].x-P[Stack.list[Stack.top-2]].x;
vv.y=P[Stack.list[Stack.top-1]].y-P[Stack.list[Stack.top-2]].y;
v.x=P[Stack.list[Stack.top]].x-P[Stack.list[Stack.top-1]].x;
v.y=P[Stack.list[Stack.top]].y-P[Stack.list[Stack.top-1]].y;
if(CP(v,vv)<0)
Stack.list[--Stack.top]=i;
}
// for(i=1;i<=Stack.top;i++)
// fout<<P[Stack.list[i]].x<<" "<<P[Stack.list[i]].y<<endl;
}
double Len(int a,int b)
{
return sqrt(double(P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y));
}
Point point[200000],*px[200000],*py[200000];
inline double dis(Point *a,Point *b)
{
return hypot((a->x-b->x),(a->y-b->y));
}
inline double min(double a,double b)
{
return a < b ? a : b;
}
double closest(int l,int r)
{
if(l+1 == r)
return dis(px[l],px[r]);
if(l+2 == r)
return min(dis(px[l],px[l+1]),min(dis(px[l+1],px[r]),dis(px[l],px[r])));
int mid = (l+r)/2;
double ans = min(closest(l,mid),closest(mid+1,r));
int i,cnt = 0,j;
for(i = l; i <= r; i++)
if(px[i]->x >= px[mid]->x-ans && px[i]->x <= px[mid]->x+ans)
py[cnt++] = px[i];
sort(py,py+cnt,cmpy);
for(i = 0; i < cnt; i++)
for(j = i+1; j < cnt; j++)
{
if(py[j]->y - py[i]->y >= ans)
break;
ans = min(ans,dis(py[i],py[j]));
}
return ans;
}
void Solve()
{
Graham_Scan();
int i,j;double Max=0,ans;
for(i=1;i<=Stack.top;i++)
for(j=i+1;j<=Stack.top;j++)
Max=max(Max,Len(Stack.list[i],Stack.list[j]));
fout<<setiosflags(ios::fixed)<<setprecision(6)<<Max<<endl;
n=N;
for(i = 0; i < n; i++)
{
point[i].x=P[i+1].x;point[i].y=P[i+1].y;
px[i] = &point[i];
}
sort(px,px+n,cmpx);
ans = closest(0,n-1);
fout<<setiosflags(ios::fixed)<<setprecision(6)<<ans<<endl;
}
int main()
{
Initialize();
Solve();
fin.close();
fout.close();
return 0;
}