| ||||||||||
| 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