HDU 5784 How Many Triangles（计算几何）

超、凢脫俗 2022-09-25 06:29 13阅读 0赞

计算几何小知识：http://blog.csdn.net/q610376681/article/details/52215024  
（包括了这里用到的计算几何知识）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5784

题目大意：给你n个不重合的点，问你能组成多少个锐角三角形

解题思路：计算出所有点能组成的锐角个数A，直角和钝角个数B，答案为(A-2B)/3,注意不包括平角，因为它什么也组不成。  
统计角的方法为对每个点先进行极角排序，针对一个点i，极角排序后再将所有点复制一遍存储，遍历排序后的每个点j，用滑动窗口维护与点i和点j成90度与180度的区间，注意对一条线上的点要特殊处理。（主要是难在写代码上。。。）

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    struct P
    {
        LL x;
        LL y;
        double t;
    };
    
    bool cmp(P p1,P p2)
    {
        return p1.t<p2.t;
    }
    
    LL dianji(P p1,P p2)
    {
        return p1.x*p2.x+p2.y*p1.y;
    }
    
    LL chaji(P p1,P p2)
    {
        return p1.x*p2.y-p2.x*p1.y;
    }
    
    bool equ(P p1,P p2)
    {
        if(p1.x==p2.x&&p1.y==p2.y)   return false;
        return true;
    }
    
    bool judge1(P p1,P p2)
    {
        if(equ(p1,p2)&&dianji(p1,p2)>0&&chaji(p1,p2)>=0) return true;
        return  false;
    
    }
    bool judge2(P p1,P p2)
    {
        if(equ(p1,p2)&&dianji(p1,p2)<=0&&chaji(p1,p2)>0) return true;
        return false;
    }
    int main()
    {
        int n;
        while(RI(n)!=EOF)
        {
            P p[2005];
            int  ruijiao=0,feiruijiao=0;
            for(int i=0; i<n; i++)
            {
                LL x,y;
                scanf("%I64d %I64d",&x,&y);
                p[i].x=x;
                p[i].y=y;
            }
    
            for(int i=0; i<n; i++)
            {
                P pp[4010];
                int len=0;
    
                for(int j=0; j<n; j++)
                    if(j!=i) pp[len++]=p[j];
                for(int j=0; j<len; j++)
                {
                    pp[j].x-=p[i].x;
                    pp[j].y-=p[i].y;
                    pp[j].t=atan2(pp[j].y,pp[j].x);
                }
    
                sort(pp,pp+len,cmp);
                for(int j=0; j<n-1; j++)
                    pp[len++]=pp[j];
                int chongdian=1,rAnglePoi=1,OAnglePoi=0;;
                for(int j=0; j<n-1; j++)
                {
                    chongdian=1;
                    if(rAnglePoi<=j) rAnglePoi=j+1;
                    while(judge1(pp[j],pp[rAnglePoi])) rAnglePoi++;
                    if(OAnglePoi<rAnglePoi)  OAnglePoi=rAnglePoi;
                    while(judge2(pp[j],pp[OAnglePoi])) OAnglePoi++;
                    while(j<n-2&&pp[j].t==pp[j+1].t)
                    {
                        j++;
                        chongdian++;
                    }
                    ruijiao+=(rAnglePoi-j-1)*chongdian;
                    feiruijiao+=(OAnglePoi-rAnglePoi)*chongdian;
                }
            }
            printf("%d\n",(ruijiao-2*feiruijiao)/3);
        }
    
        return 0;
    }