| ||||||||||
| 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 | |||||||||
为什么WA!求大神
#include <stdio.h>
#include <math.h> //gcc需加-lm参数
#include <cmath>
#define eps 0.0000001
#define PI 3.141592654 //PI = acos(-1.0);
#define zero(x)(((x)>0?(x):-(x))<eps)
using namespace std;
struct POINT
{
double x;
double y;
};
struct line
{
POINT a,b;
};
double dist(POINT p1,POINT p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double multiply(POINT sp,POINT ep,POINT op)
{
return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
}
double xmult(POINT p1,POINT p2,POINT p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//判断点是否在线段上
int dog(POINT p,line l)
{
return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
}
int dog1(POINT p,line l)
{
return dog(p,l)&&(!zero(p.x-l.a.x)||!zero(p.y-l.a.y))&&(!zero(p.x-l.b.x)||!zero(p.y-l.b.y));
}
int Graham_scan(POINT PointSet[],POINT ch[],int n)
{
int i,j,k=0,top=2,len;
POINT tmp;
for(i=1; i<n; i++)
if ( PointSet[i].y<PointSet[k].y || (PointSet[i].y==PointSet[k].y) && (PointSet[i].x<PointSet[k].x) )
k=i;
tmp=PointSet[0];
PointSet[0]=PointSet[k];
PointSet[k]=tmp; // 现在PointSet中y坐标最小的点在PointSet[0]
for (i=1; i<n-1; i++) /* 对顶点按照相对PointSet[0]的极角从小到大进行排序,极角相同的按照距离PointSet[0]从近到远进行排序 */
{
k=i;
for (j=i+1; j<n; j++)
if ( multiply(PointSet[j],PointSet[k],PointSet[0])>0 || // 极角更小
(multiply(PointSet[j],PointSet[k],PointSet[0])==0) && /* 极角相等,距离更短 */
dist(PointSet[0],PointSet[j])<dist(PointSet[0],PointSet[k])
)
k=j;
tmp=PointSet[i];
PointSet[i]=PointSet[k];
PointSet[k]=tmp;
}
ch[0]=PointSet[0];
ch[1]=PointSet[1];
ch[2]=PointSet[2];
//用数组模拟栈,top为栈顶
for (i=3; i<n; i++)
{
while (multiply(PointSet[i],ch[top],ch[top-1])>=0)
top--;
ch[++top]=PointSet[i];
}
len=top+1;
return len;
}
int main()
{
int N,L;
scanf("%d",&L);
while(L--)
{
scanf("%d",&N);
int i,j;
POINT PointSet[1001],ch[1001];
for(i=0; i<N; i++)
{
scanf("%lf%lf",&PointSet[i].x,&PointSet[i].y);
}
j=Graham_scan(PointSet,ch,N);
// Graham_scan(PointSet,ch,N);
int s=0,k,ss=0;
line l;
int q=0;
for(i=1; i<j; i++)
{
if(ch[0].y==ch[i].y)
q++;
else
break;
}
l.a=ch[0];
l.b=ch[q];
for( k=0; k<N; k++)
{
if(dog1(PointSet[k],l))
{
s++;
break;
}
}
// printf("%d %d\n",s,q);
for(i=q; i<j; i++)
{
l.a=ch[q];
l.b=ch[q+1];
for( k=0; k<N; k++)
{
if(dog1(PointSet[k],l))
{
s++;
break;
}
}
}
// printf("%d\n",s);
for( k=0; k<N; k++)
{
l.a=ch[0];
l.b=ch[j-1];
if(dog1(PointSet[k],l))
{
s++;
break;
}
}
// printf("%d\n",s);
if(s==j)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
/*
1)此题需要判断“凸包上每条边至少包含原多边形三个点”。成立就是“YES”。
我试的判断“多边形上 所有点 在凸包上”,WA!!
(2)注意:所有点共线时,结果为“NO”。
*/
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator