Question

Beauty Contest poj2187求凸包的题WA啊！ 求大神帮忙看下错在哪！！！求解救啊！

我的代码：
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define N 50005
using namespace std;
struct point{
int x,y;
}pt[N];
int convex[N];
int n,k;
int dist(int a,int b){
return (pt[a].x-pt[b].x)*(pt[a].x-pt[b].x)+(pt[a].y-pt[b].y)*(pt[a].y-pt[b].y);
}
bool cmp(point a,point b)
{
if((a.x-pt[0].x)*(b.y-pt[0].y)==(b.x-pt[0].x)*(a.y-pt[0].y))
return ((a.x-pt[0].x)*(a.x-pt[0].x)+(a.y-pt[0].y)*(a.y-pt[0].y))<((b.x-pt[0].x)*(b.x-pt[0].x)+(b.y-pt[0].y)*(b.y-pt[0].y));
return ((a.x-pt[0].x)*(b.y-pt[0].y)>(b.x-pt[0].x)*(a.y-pt[0].y));
}
bool Left(int a,int b,int c){
int x1=pt[b].x-pt[a].x;
int y1=pt[b].y-pt[a].y;
int x2=pt[c].x-pt[b].x;
int y2=pt[c].x-pt[b].y;
if(x1*y2>y1*x2)return true;
return false;
}
int max(int a,int b){
return a>b?a:b;
}
void swap(int a,int b){
int temp;
temp=pt[a].x;
pt[a].x=pt[b].x;
pt[b].x=temp;
temp=pt[a].y;
pt[a].y=pt[b].y;
pt[b].y=temp;
}
int main()
{
//freopen("in.txt","r",stdin);
int t,ans,i,j;
while(scanf("%d",&n)!=EOF){
k=t=ans=0;
for(i=0;i<n;i++){
scanf("%d %d",&pt[i].x,&pt[i].y);
if((pt[i].y<pt[k].y)||((pt[k].y==pt[i].y)&&(pt[i].x<pt[k].x)))
k=i;
}
if(k!=0){
swap(k,0);
}
sort(pt+1,pt+n,cmp);
//for(i=0;i<n;i++)
// printf("%d %d\n",pt[i].x,pt[i].y);
convex[t++]=0;
convex[t++]=1;
convex[t++]=2;
for(i=3;i<n;){
if(t<2||Left(convex[t-2],convex[t-1],i))
convex[t++]=i++;
else --t;
}
for(i=0;i<t;i++){
for(j=i+1;j<t;j++)
ans=max(ans,dist(convex[i],convex[j]));
}
printf("%d\n",ans);
}
return 0;
}
这题我都调试一天半了，还没找到是哪错了，唉，弱啊！！

Answer 1

这是AC代码，你看下错在哪，就知道了。还有你应该对凸包掌握的还不是很牢固，不然这样的题应该秒杀的！
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 50005
using namespace std;
struct point{
int x,y;
}pt[N];
int convex[N];
int n;
int xmult(point a,point b,point c){
return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}
int dist(point a,point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(point a,point b)
{
if(xmult(pt[0],a,b)>0||(xmult(pt[0],a,b)==0&&dist(a,pt[0])<dist(b,pt[0])))return true;
return false;
}
bool left(int a,int b,int c){
if(xmult(pt[a],pt[b],pt[c])>0)return true;
return false;
}
int max(int a,int b){
return a>b?a:b;
}
int main()
{
//freopen("in.txt","r",stdin);
int i,j,k,ans,top;
while(scanf("%d",&n)!=EOF){
k=top=ans=0;
for(i=0;i<n;i++){
scanf("%d %d",&pt[i].x,&pt[i].y);
if(pt[i].y<pt[k].y)
k=i;
else if(pt[i].y==pt[k].y&&pt[i].x<pt[k].x)
k=i;
}
if(k){
swap(pt[k].x,pt[0].x);
swap(pt[k].y,pt[0].y);
}
sort(pt+1,pt+n,cmp);
convex[top++]=0;
convex[top++]=1;
convex[top++]=2;
for(i=3;i<n;){
if(top<2||left(convex[top-2],convex[top-1],i))
convex[top++]=i++;
else top--;
}
for(i=0;i<top;i++){
for(j=i+1;j<top;j++)
ans=max(ans,dist(pt[convex[i]],pt[convex[j]]));
}
printf("%d\n",ans);
}
return 0;
}