Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么WA!求大神

Posted by 112103111 at 2013-11-17 21:51:50 on Problem 1228
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator