【LOJ3054】【HNOI2019】鱼_综合

Description

https://loj.ac/problem/3054

Solution

枚举 $A$ 、 $D$ ，鱼身和鱼尾分别处理。
考虑鱼身，可以枚举两个点，将它们的中点放在中垂线上，具体来说可以开个map，然后记一下这条中垂线 $a x + b y + c = 0$ 的最简形式，强制 $a > 0$ 或 $b > 0$ ，然后给每条这样的直线开个vector存中点，后面枚举 $A$ 、 $D$ 时直接在上面二分即可。
至于鱼尾，可以枚举每个点，将其它点极角排序，枚举 $A$ 、 $D$ 时两个指针扫，要注意鱼尾可以同时在直线 $A D$ 一边。实现时可以把点复制一遍，后面的点的极角加上 $2\pi$ ，判断时用极角就很方便了。
~~还有就是比赛时别肝这题~~

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<assert.h>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pr;
const double eps=1e-10,pi=acos(-1);
const ll inf=1e15;
const int N=1010;
struct P{
    ll x,y;double ang;P(){
    }P(ll _x,ll _y) {
    x=_x,y=_y,ang=atan2(y,x);}friend bool operator <(P x,P y){
    return x.ang<y.ang;}
}a[N],b[N*2];
P operator -(P x,P y) {
    return P(x.x-y.x,x.y-y.y);}
P operator +(P x,P y) {
    return P(x.x+y.x,x.y+y.y);}
P operator *(P x,ll y) {
    return P(x.x*y,x.y*y);}
ll dot(P x,P y) {
    return x.x*y.x+x.y*y.y;}
ll cross(P x,P y) {
    return x.x*y.y-x.y*y.x;}
typedef vector<pr> vec;
ll gcd(ll x,ll y){
    return !y?x:gcd(y,x%y);
}
ll Abs(ll x){
    return x<0?-x:x;
}
struct node{
    ll a,b,c;node(){
    }node(ll _a,ll _b,ll _c){
    ll g=gcd(gcd(Abs(_a),Abs(_b)),Abs(_c));a=_a/g,b=_b/g,c=_c/g;if(a<0) a=-a,b=-b,c=-c;else if(!a && b<0) b=-b,c=-c;}friend bool operator <(node x,node y){
    if(x.a==y.a) return x.b<y.b || (x.b==y.b && x.c<y.c);else return x.a<y.a;}
};
map<node,vec> mp;
int tot,now;
bool cmp(P x,P y){
    double t1=atan2(x.y,x.x),t2=atan2(y.y,y.x);return fabs(t1-t2)<eps?x.x<y.x:t1<t2;
}
ll tmp;
ll calc(P x,P y){
    if(x.x>y.x || (x.x==y.x && x.y>y.y)) swap(x,y);node w(x.y-y.y,y.x-x.x,x.x*y.y-x.y*y.x);if(!mp.count(w)) return 0;vec t=mp[w];pr t1=make_pair(x.x*2,inf),t2=make_pair(y.x*2,-inf);if(x.x==y.x) t1.se=x.y*2,t2.se=y.y*2;int l=upper_bound(t.begin(),t.end(),t1)-t.begin(),r=lower_bound(t.begin(),t.end(),t2)-t.begin();return r-l;
}
vec px;
ll re[N],d[N],vl[N*2];
int c[N];
int main()
{
    freopen("fish.in","r",stdin);freopen("fish.out","w",stdout);int n;scanf("%d",&n);fo(i,1,n){
    P q;scanf("%lld %lld",&q.x,&q.y);a[i]=q;fo(j,1,i-1){
    P p=a[j];node w=node(2*(p.x-q.x),2*(p.y-q.y),q.x*q.x-p.x*p.x+q.y*q.y-p.y*p.y);mp[w].push_back(make_pair(p.x+q.x,p.y+q.y));}}for(map<node,vec>::iterator i=mp.begin();i!=mp.end();++i){
    px=i->second;sort(px.begin(),px.end());mp[i->first]=px;}ll ans=0;fo(i,1,n){
    tot=0,now=i;fo(j,1,n) if(i!=j) b[++tot]=a[j]-a[now];sort(b+1,b+tot+1);fo(i,1,tot) b[i+tot]=b[i],b[i+tot].ang+=2*pi;int ln=tot<<1,l=0,r=0;fo(j,1,tot) re[j]=dot(b[j],b[j]),d[j]=re[j];sort(d+1,d+tot+1);int cn=unique(d+1,d+tot+1)-d-1;fo(j,1,tot) vl[j]=lower_bound(d+1,d+cn+1,re[j])-d;fo(j,1,tot) vl[j+tot]=vl[j];fo(j,1,cn) c[j]=0;ll tmp=0;fo(j,1,tot){
    for(;r<=ln && b[r+1].ang+eps<b[j].ang+1.5*pi;) ++r,tmp+=c[vl[r]],++c[vl[r]];for(;l<=ln && b[l+1].ang<b[j].ang+0.5*pi+eps;) ++l,--c[vl[l]],tmp-=c[vl[l]];int t=calc(a[now],b[j]+a[now]);ans+=tmp*t;}}printf("%lld",ans<<2);
}