| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:TLE为什么老是这样啊In Reply To:TLE为什么老是这样啊 Posted by:ACM1900 at 2010-08-10 16:32:19 改成这样过的。不止是cin的原因应该……
#include <stdio.h>
#include <math.h>
#include<algorithm>
using namespace std;
#define Max 50001
struct Point
{ int x,y;};
Point p[Max];int stack[Max];
int top,n;
int dis(Point p1,Point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int cross(Point p1,Point p2,Point p3)
{ return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);}
bool comp(Point p1,Point p2)
{ if(p1.y==p2.y)
return p1.x<p2.x;
else
return p1.y<p2.y;
}
void graham()
{
int i,j; if(n<=1)
{ top=1;
return ;
}
sort(p+1,p+n+1,comp);
top=0;
stack[++top]=1;
stack[++top]=2;
for(i=3;i<=n;++i)
{ if(top>=2&&cross(p[stack[top-1]],p[i],p[stack[top]])>=0)--top;
stack[++top]=i;
}
int temptop=top;
stack[++top]=n-1;
for(i=n-2;i>=1;--i)
{ if(top>=temptop+1&&cross(p[stack[top-1]],p[i],p[stack[top]])>=0)--top;
stack[++top]=i;
}
int max=-1,tem;
for(i=1;i<=top;++i)
{ for(j=i+1;j<=top;++j)
{ tem=dis(p[stack[i]],p[stack[j]]);
if( tem>max )
max=tem;
}
}
printf("%d\n",max);
return ;
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{ for(i=1;i<=n;i++)
scanf("%d %d",&p[i].x,&p[i].y);
graham();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator