HDU 5738 Eureka（计算几何）

末蓝、 2022-07-20 12:17 154阅读 0赞

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

题目大意：给你许多点，这些点能组成许多条直线，一条直线上可能的点  
的组合为x，问所有直线的x加起来是多少。

解题思路：先对所有点按x进行从左到右的排序，对每一个点进行极角排序，再扫描其右部分的的所有点，注意重点情况的组合数的计算。详情见代码。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include<cmath>
    #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+7;
    const int inf1=-1*1e9;
    double EPS=1e-12;
    typedef long long LL;
    struct P
    {
        double x;
        double y;
        double rad;//点atan2值 大小为-180到180
    };
    
    P p[1005];
    
    bool cmp(P p1,P p2)
    {
        if(p1.x==p2.x) return p1.y<p2.y;
        else return p1.x<p2.x;
    }
    
    bool cmp1(P p1,P p2)
    {
        return p1.rad<p2.rad;
    }
    
    bool equ(double a,double b)
    {
        if(abs(a-b)<EPS) return true;
        else return false;
    }
    LL mod_pow(LL x,LL n)
    {
        LL res=1;
        while(n>0)
        {
            if(n&1) res=res*x%inf;
            x=(x%inf)*(x%inf)%inf;
            n>>=1;
        }
        return res;
    }
    
    int main()
    {
        int T;
        RI(T);
        while(T--)
        {
            LL ans=0;
    
            int n;
            RI(n);
            for(int i=0; i<n; i++)
                scanf("%lf%lf",&p[i].x,&p[i].y);
    
            sort(p,p+n,cmp);//按x对所有点排序
            for(int i=0; i<n-1; i++)//对点i进行极角怕排序
            {
                P pp[1005];
                LL t=0;
                int len=0;//点i右边的所有点的个数
    
                /*正常排序要所有点，但这里我们只需要右边的点
                所以这里我们只对右边的点排序*/
    
                for(int j=i+1; j<n; j++)//将点i右边的加进序列
                {
                    if(p[j].x==p[i].x&&p[j].y==p[i].y)//重点统计并跳过
                    {
                        t++;
                        continue;
                    }
                    pp[len]=p[j];
                    pp[len].x-=p[i].x;
                    pp[len].y-=p[i].y;
                    pp[len].rad=atan2(pp[len].y,pp[len].x);//计算atan2
                    len++;
                }
    
                sort(pp,pp+len,cmp1);
                LL num;
                if(len>=1)  num=1;
                else num=0;
                double preRad=pp[0].rad;
                for(int j=1; j<len; j++)
                {
                    while(j<len&&equ(preRad,pp[j].rad))//统计一条线上的点
                    {
                        j++;
                        num++;
                    }
    
                    if(j<len)
                    {
                        ans=(ans+mod_pow(2,num+t)-1)%inf;
                        if(t>0) ans=((ans-mod_pow(2,t)+1)+inf)%inf;//减去重点的值
                        num=1;
                        preRad=pp[j].rad;
                    }
                }
    
                ans=(ans+mod_pow(2,num+t)-1)%inf;
            }
            cout<<ans<<endl;
    
    
        }
    
        return 0;
    }