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