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 |
望大神指点错哪儿了。#include <stack> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct point { int x; int y; } p[50010]; int cross(point a,point b,point c) { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int cmp1(point a,point b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } bool cmp2(point a,point b) { if(cross(a,b,p[0])>0) return true; if(cross(a,b,p[0])<0) return false; if(cross(a,b,p[0])==0) dis(a,p[0])-dis(b,p[0])<=0?true:false; } int main() { int n; point s[50010]; while(scanf("%d",&n)&&n!=-1) { for(int i=0; i<n; i++) scanf("%d%d",&p[i].x,&p[i].y); if(n<=2) { printf("0.00\n"); continue; } sort(p,p+n,cmp1); sort(p+1,p+n,cmp2); memset(s,0,sizeof(s)); s[0]=p[0]; s[1]=p[1]; int top=1; for(int i=2; i<n; i++) { while(i>=1&&cross(p[i],s[top],s[top-1])>=0) top--; s[++top]=p[i]; } if(n<=2) { printf("0.00\n"); continue; } s[++top]=p[0]; int ans=0; for(int i=0; i<top; i++) { int q=1; for(int j=i+1; j<=top; j++) { while(cross(s[i],s[j],s[q+1])>cross(s[i],s[j],s[q])) q=(q+1)%top; ans=max(ans,cross(s[i],s[j],s[q])); } } double res=double(ans/2.0); printf("%.2lf\n",res); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator