题目分析

不难发现需要枚举 D 和 A,然后鱼头鱼尾分别处理。

对于鱼尾,其实就是对着 A 的半平面内两条到 D 距离相等的线段组成的,枚举 D 后,将其他点极角排序,然后扫描线即可解决。

对于鱼头,也就是 BC 这条线段要垂直于 AD,且 BC 的中点在 AD 上。则预处理枚举每个 BC,将这个点对存入它的垂直平分线的 vector 中,按照中点排序。然后枚举 AD,找到 AD 所在直线的 vector,二分查找 vector 中中点在 AD 上的点对有多少个。

用了一堆 map 和 vector,不开 O2 没法过。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
const int N=1005;
const db pi=acos(-1),eps=1e-10;
int n,lcnt;LL ans,tail_ans[N][N];
struct point{LL x,y;}p[N];

map<uLL,int> mp;
map<LL,int> mp_tail;
vector<int> ppair[1000005];
LL gcd(LL x,LL y) {return y?gcd(y,x%y):x;}
void head_prework() {
    for(RI i=1;i<=n;++i)
        for(RI j=i+1;j<=n;++j) {
            LL A=p[i].x-p[j].x,B=p[i].y-p[j].y,C,d=gcd(abs(A),abs(B));
            LL midx=(p[i].x+p[j].x)/2,midy=(p[i].y+p[j].y)/2;
            if(A<0||(A==0&&B<0)) A=-A,B=-B;
            A/=d,B/=d,C=-midx*A-midy*B;
            uLL has=A*100000007+B*10007+C;
            if(!mp[has]) mp[has]=++lcnt;
            ppair[mp[has]].push_back(p[i].y==p[j].y?midy:midx);
        }
    for(RI i=1;i<=lcnt;++i) sort(ppair[i].begin(),ppair[i].end());
}
void head_work() {
    for(RI i=1;i<=n;++i)
        for(RI j=i+1;j<=n;++j) {
            LL A=p[i].y-p[j].y,B=p[j].x-p[i].x,C,d=gcd(abs(A),abs(B));
            if(A<0||(A==0&&B<0)) A=-A,B=-B;
            A/=d,B/=d,C=-p[i].x*A-p[i].y*B;
            uLL has=A*100000007+B*10007+C;
            LL k1=(p[i].x==p[j].x?p[i].y:p[i].x);
            LL k2=(p[i].x==p[j].x?p[j].y:p[j].x);
            if(k1>k2) swap(k1,k2);
            LL nowans=0;
            if(mp.count(has)) {
                uLL t=mp[has];
                nowans=lower_bound(ppair[t].begin(),ppair[t].end(),k2)-
                upper_bound(ppair[t].begin(),ppair[t].end(),k1);
            }
            ans+=nowans*(tail_ans[i][j]+tail_ans[j][i]);
        }
}

struct Apoint{int id;db jd;}kp[N<<1];
bool cmp(Apoint A,Apoint B) {return A.jd<B.jd;}
LL getdis(int a,int b)
    {return (p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y);}
void tail_work() {
    for(RI i=1;i<=n;++i) {//D
        int m=0;
        for(RI j=1;j<=n;++j)
            if(j!=i) kp[++m]=(Apoint){j,atan2(p[j].y-p[i].y,p[j].x-p[i].x)};
        sort(kp+1,kp+1+m,cmp);
        for(RI j=1;j<=m;++j) kp[j+m]=kp[j],kp[j+m].jd+=pi+pi;
        LL nowans=0;mp_tail.clear();
        for(RI j=1,L=1,R=0;j<=m;++j) {//A
            while(kp[R+1].jd+eps<kp[j].jd+1.5*pi)
                ++R,nowans+=mp_tail[getdis(i,kp[R].id)]++;
            while(kp[L].jd<kp[j].jd+0.5*pi+eps)
                nowans-=--mp_tail[getdis(i,kp[L].id)],++L;
            tail_ans[i][kp[j].id]=nowans;
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(RI i=1;i<=n;++i)
        scanf("%lld%lld",&p[i].x,&p[i].y),p[i].x*=2,p[i].y*=2;
    head_prework(),tail_work(),head_work();
    printf("%lld\n",ans*4);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注