M_sea

洛谷5286 [HNOI2019]鱼
LuoguLOJ分析口胡一时爽,写题火葬场显然可以枚举 $A$ 和 $D$ ,再算 $EF$ 和 $BC$ 的方案...
扫描右侧二维码阅读全文
03
2019/06

洛谷5286 [HNOI2019]鱼

Luogu

LOJ

分析

口胡一时爽,写题火葬场

显然可以枚举 $A$ 和 $D$ ,再算 $EF$ 和 $BC$ 的方案数。

$EF$ 比较好算:按极角序枚举 $A$ ,那么直接双指针扫所有的点并类似莫队更新答案即可。

$BC$ 就比较难算。注意到 $AD$ 对 $BC$ 的限制很强,那么我们可以先枚举 $B$ 和 $C$ ,然后把 $BC$ 的中点插入 $BC$ 的垂直平分线的 $\mathrm{vector}$ 中。那么对于一组 $AD$ ,直接在 $\mathrm{vector}$ 中二分就可以求出 $BC$ 的组数了。

代码细节比较多,另外还要注意精度问题。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
const double eps=1e-10;

struct frac {
    ll x,y;
    frac(ll x_=0,ll y_=0) {
        ll d=__gcd(abs(x_),abs(y_));
        x=x_/d,y=y_/d;
        if (y<0) x=-x,y=-y;
    }
    inline void print() { printf("%lld/%lld ",x,y); }
};
bool operator <(frac a,frac b) { return a.x!=b.x?a.x<b.x:a.y<b.y; }
bool operator !=(frac a,frac b) { return a.x!=b.x||a.y!=b.y; }

struct line { frac k,b; };
bool operator <(line a,line b) { return a.k!=b.k?a.k<b.k:a.b<b.b; }

struct point { int x,y; } p[N];

struct node { int id; double ang; } sta[N<<1];
bool operator <(node a,node b) { return a.ang<b.ang; }
int top=0;

map<line,int> M; int cnt=0;
vector<int> vec[N*N];
int EF[N][N];

inline ll sqr(int x) { return 1ll*x*x; }
inline ll dis(int i,int j) {
    return sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y);
}

map<ll,int> num; int sum=0;
inline void add(int x,int i) { sum+=num[dis(x,i)],++num[dis(x,i)]; }
inline void del(int x,int i) { --num[dis(x,i)],sum-=num[dis(x,i)]; }

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
    
    //预处理BC
    for (re int i=1;i<=n;++i)
        for (re int j=i+1;j<=n;++j) {
            if (p[i].y==p[j].y) {
                frac k=(frac){1,0},b=(frac){p[i].x+p[j].x,2};
                line l=(line){k,b};
                if (M.find(l)==M.end()) M[l]=++cnt;
                vec[M[l]].push_back(p[i].y*2);
            } else {
                frac k=(frac){p[i].x-p[j].x,p[j].y-p[i].y};
                frac b=(frac){-1ll*(p[i].x-p[j].x)*(p[i].x+p[j].x)+1ll*(p[j].y-p[i].y)*(p[j].y+p[i].y),2ll*(p[j].y-p[i].y)};
                line l=(line){k,b};
                if (M.find(l)==M.end()) M[l]=++cnt;
                vec[M[l]].push_back(p[i].x==p[j].x?p[i].x*2:p[i].y+p[j].y);
            }
        }

    //计算所有AD对应的EF方案数
    for (re int i=1;i<=n;++i) {
        int top=0;
        for (re int j=1;j<=n;++j)
            if (i!=j) sta[++top]=(node){j,atan2(p[j].y-p[i].y,p[j].x-p[i].x)};
        sort(sta+1,sta+top+1);
        for (re int j=1;j<=top;++j) sta[j+top]=sta[j],sta[j+top].ang+=2*M_PI;
        num.clear(); sum=0;
        for (re int j=1,h=0,t=0;j<=top;++j) {
            while (sta[h+1].ang+eps<sta[j].ang+1.5*M_PI) add(sta[++h].id,i);
            while (sta[t+1].ang<sta[j].ang+0.5*M_PI+eps) del(sta[++t].id,i);
            EF[sta[j].id][i]=sum;
        }
    }
    
    //计算所有AD对应的BC方案数并计算答案
    for (re int i=1;i<=cnt;++i) sort(vec[i].begin(),vec[i].end());
    ll ans=0;
    for (re int i=1;i<=n;++i)
        for (re int j=i+1;j<=n;++j) {
            frac k,b;
            if (p[i].x==p[j].x) k=(frac){1,0},b=(frac){p[i].x,1};
            else k=(frac){p[i].y-p[j].y,p[i].x-p[j].x},b=(frac){-1ll*p[i].x*(p[i].y-p[j].y)+1ll*p[i].y*(p[i].x-p[j].x),p[i].x-p[j].x};
            line l=(line){k,b};
            if (M.find(l)==M.end()) continue;
            int L=p[i].y,R=p[j].y;
            if (L==R) L=p[i].x,R=p[j].x;
            if (L>R) swap(L,R);
            ans+=(upper_bound(vec[M[l]].begin(),vec[M[l]].end(),R*2-1)-
                  upper_bound(vec[M[l]].begin(),vec[M[l]].end(),L*2))
                *(EF[i][j]+EF[j][i]);
        }
    printf("%lld\n",ans*4);
    return 0;
}
最后修改:2019 年 06 月 05 日 03 : 19 PM

4 条评论

  1. smy

    下午还说代码细节不多的

    1. M_sea
      @smy

      不是很多=比较多

      1. Siyuan
        @M_sea

        M_sea:口胡 = 懒得写正解(逃

        1. M_sea
          @Siyuan

          可是这题正解好难写的嘤

发表评论 取消回复