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

乱七八糟地2A了。

Posted by StepByStepCnmLife at 2015-05-14 23:19:20 on Problem 1228
#include <stdio.h>
#include <stdlib.h>
#define MAX 1010
#define swap(a,b)  a=a+b,b=a-b,a=a-b
typedef struct Point{
    int x;
    int y;
}Point;
Point pset[MAX];
int cross(Point origin,Point A,Point B)
{
    return ( (A.x-origin.x)*(B.y-origin.y)-(B.x-origin.x)*(A.y-origin.y) );
}
int cmp(const void *A,const void *B)
{
    return -cross(pset[0],*(Point*)A,*(Point*)B);
}
int main()
{
    int tc,n,i,j,status,flag;
    Point temp;
    scanf("%d",&tc);
    for(j=0;j<tc;j++)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        scanf("%d%d",&pset[i].x,&pset[i].y);
        if(n<6)
        {
            printf("NO\n");
            continue;
        }
        for(i=1;i<n;i++)//寻找基点
        {
            if(pset[i].y<pset[0].y||(pset[i].y==pset[0].y&&pset[i].x<pset[0].x))
            {
                swap(pset[i].x,pset[0].x);
                swap(pset[i].y,pset[0].y);
            }
        }
        qsort(pset+1,n-1,sizeof(Point),cmp);
        for(i=1;i<(n-1);i++)
        {
            if(cross(pset[0],pset[i],pset[i+1])==0)
            if(pset[i].x>pset[i+1].x||pset[i].y>pset[i+1].y)
            {

                temp=pset[i];
                pset[i]=pset[i+1];
                pset[i+1]=temp;
            }
        }
        i=n-2;
        while(cross(pset[0],pset[n-1],pset[i])==0&&i!=0)i--;
        i++;//i refer to the last edge && the minest x coordinat
        swap(pset[i].x,pset[n-1].x);
        swap(pset[i].y,pset[n-1].y);
        if(i==(n-1)){printf("NO\n");continue;}//最后一条边不满足条件
        else if(i==0){printf("NO\n");continue;}
        status=i;
        for(i=0,flag=0;i<(n-1);i++)
        {
            if(i==status)
            {
                flag=1;
                break;
            }
            if (cross(pset[i],pset[i+1],pset[i+2])==0)
            {
                i++;
                while(cross(pset[i],pset[i+1],pset[i+2])==0)i++;
            }
            else
            {
                flag=0;
                break;
            }
        }
        if(flag==0)printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

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