poj 1228 Grandpa's Estate

今天药忘吃喽~ 2023-08-17 15:33 82阅读 0赞

> 题目衔接：[http://poj.org/problem?id=1228][http_poj.org_problem_id_1228]

> <table> 
>  <tbody> 
>   <tr> 
>    <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
>    <td>&nbsp;</td> 
>    <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
>   </tr> 
>   <tr> 
>    <td><strong>Total Submissions:</strong>&nbsp;16821</td> 
>    <td>&nbsp;</td> 
>    <td><strong>Accepted:</strong>&nbsp;4725</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> Description
> 
> Being the only living descendant of his grandfather, Kamran the Believer inherited all of the grandpa's belongings. The most valuable one was a piece of convex polygon shaped farm in the grandpa's birth village. The farm was originally separated from the neighboring farms by a thick rope hooked to some spikes (big nails) placed on the boundary of the polygon. But, when Kamran went to visit his farm, he noticed that the rope and some spikes are missing. Your task is to write a program to help Kamran decide whether the boundary of his farm can be exactly determined only by the remaining spikes.
> 
> Input
> 
> The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains an integer n (1 <= n <= 1000) which is the number of remaining spikes. Next, there are n lines, one line per spike, each containing a pair of integers which are x and y coordinates of the spike.
> 
> Output
> 
> There should be one output line per test case containing YES or NO depending on whether the boundary of the farm can be uniquely determined from the input.

>  
> 
> Sample Input
> 
>     1
>     6 
>     0 0
>     1 2
>     3 4
>     2 0
>     2 4 
>     5 0
> 
> Sample Output
> 
>     NO

>  题目大意：给你n个点，问你由这些点构成的多边形是不是稳定的
> 
> 思路：什么叫稳定多边形？就是不会变的那种，什么叫不会变？就是一条线段上有三个点，这三个点可以固定这条线段，那么组成这个多边形的每个边都是稳定的那么这个多边形也是稳定的，我们可以先求出这是不是一个由至少三个点构成的凸包，然后枚举每条边上是否存在多余的点（PS；我的代码里面写的是直接判断叉积，不知道为啥写判断点是否在线段上的另一种办法是错误的，wa到吐）

另一种判断点是否在线段上的方法：

>     ///判断点c是否在线段ab上
>     int judge(point a,point b,point c)
>     {
>             ///c若在ab上c点的横纵坐标一定在ab范围内
>         if(c.x>=min(a.x,b.x)&&c.x<=max(a.x,b.x)&&
>            c.y>=min(a.y,b.y)&&c.y<=max(a.y,b.y)&&
>            (c.x-a.x)*(b.uy-a.y)==(b.x-a.x)*(c.y-a.y))///判断叉积
>             return 1;
>         return 0;
>     }
> 
>

AC代码：

/*
    题目大意：给你n个点，问你这n个点能否组成一个稳定的多边形？
    
    
    思路：题意很简单，但是不好理解，什么样的多边形才能叫稳定多边形？
    由大佬思路得：当一条直线上存在至少三个点时，这个直线是稳定的
    也就是说组成这个多边形的所有边上都至少有三个点
    我们可以先建一个图，然后枚举每个点是否在这个线段上，如果没有这个凸包就是不稳定的
    */
    #include<set>
    #include<map>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define inf 0x3f3f3f
    #define bug  printf("bug\n")
    const int maxn=1e6+10;
    const double pi=acos(-1.0);
    const double esp=1e-6;
    const int N=2e2+10;
    struct point
    {
        int x,y;
        double v,l;
    };
    struct line
    {
        point st,ed;
        double k,b;
    };
    int sign(double x)
    {
        if(fabs(x)<esp)
            return 0;
        return x>0?1:-1;
    }
    double getk(line l)
    {
        if(l.st.x==l.ed.x)///斜率不存在
            return inf;
        return (l.ed.y-l.st.y)/(l.ed.x-l.st.x);
    }
    double getb(line l)
    {
        return l.ed.y-l.k*l.ed.x;
    }
    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 cmult(point a,point b,point c)///叉积
    {
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    point p[maxn];
    
    int cmp(point a,point b)
    {
        int ju=cmult(p[0],a,b);
        if(ju>0)
            return 1;
        else if(ju==0&&dis(a,p[0])<dis(b,p[0]))
            return 1;
        return 0;
    }
    int n;
    int Stack[maxn],top;
    void tb()
    {
        point p0;
        int k=0;
        p0=p[0];
        for(int i=1; i<n; i++)
        {
            if(p0.y>p[i].y||(p0.y==p[i].y&&p0.x==p[i].x))
            {
                p0=p[i];
                k=i;
            }
        }
        swap(p[k],p[0]);
        sort(p+1,p+n,cmp);
        if(n==1)
        {
            top=0;
            Stack[0]=0;
            return ;
        }
        if(n==2)
        {
            top=1;
            Stack[0]=0;
            Stack[1]=1;
            return;
        }
        if(n>2)
        {
            top=1;
            for(int i=0; i<=1; i++)
                Stack[i]=i;
            for(int i=2; i<n; i++)
            {
                while(top>0&&cmult(p[Stack[top-1]],p[Stack[top]],p[i])<=0)
                    top--;
                top++;
                Stack[top]=i;
            }
        }
    }
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d",&n);
            for(int i=0; i<n; i++)
                scanf("%d%d",&p[i].x,&p[i].y);
    
            if(n<6)
            {
                printf("NO\n");
                continue;
            }
            int flag=0;
            top=0;
            tb();///得到包围最外围的凸包
            if(top<2)
            {
                printf("NO\n");
                continue;
            }
            for(int i=0;i<=top;i++)
            {
                int mark=0;
                point a=p[Stack[i]],b=p[Stack[(i+1)%(top+1)]];
                for(int j=0;j<n;j++)
                {
                    if(p[j].x==a.x&&p[j].y==a.y)
                        continue;
                    if(p[j].x==b.x&&p[j].y==b.y)
                        continue;
                    if(!cmult(p[j],a,b))
                    {
                        mark=1;
                        break;
                    }
                }
                if(!mark)
                    flag=1;
                if(flag)
                    break;
            }
            if(flag)
                printf("NO\n");
            else
                printf("YES\n");
        }
        return 0;
    }

[http_poj.org_problem_id_1228]: http://poj.org/problem?id=1228