Codeforces956D. Contact ATC

$n \leq 100000$个飞机在坐标轴上，给坐标给速度，坐标速度异号，还有一个风速在$[-w,w]$区间，$w$比最小的速度绝对值要小。由于风速不知道，所以问有多少对飞机可能在原点相遇。

思维定势：$\frac{x_i}{v_i+v}=\frac{x_j}{v_j+v}$，$v$是风速，然后推下去，会推到一个三维偏序。。

没有观察题目性质。这个时间是关于风速单调而连续的，所以只要风速最小和风速最大这两个东西求个逆序对就行了。

似乎卡精度，用了分数。

这种题要写题解感觉最近脑子有点锈。。有没有神犇愿意帮忙除个锈啊QAQ

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 //#include<math.h>

 //#include<queue>

 //#include<vector>

 #include<algorithm>

 //#include<iostream>

 //#include<assert.h>

 using namespace std;

 int n,w;

 #define maxn 200011

 struct frac

 {

     int a,b;

     bool operator < (const frac &x) const {return 1ll*a*x.b<1ll*b*x.a;}

     bool operator == (const frac &x) const {return 1ll*a*x.b==1ll*b*x.a;}

 };

 struct Poi{frac x,y; int z;}p[maxn];

 bool cmpx(const Poi &a,const Poi &b) {return b.x<a.x || (a.x==b.x && a.y<b.y);}

 frac lisa[maxn]; int li=;

 struct BIT

 {

     int a[maxn],n;

     void clear(int m) {n=m;}

     void add(int x,int v) {for (;x<=n;x+=x&-x) a[x]+=v;}

     int query(int x) {int ans=; for (;x;x-=x&-x) ans+=a[x]; return ans;}

 }t;

 #define LL long long

 int main()

 {

     scanf("%d%d",&n,&w);

     for (int i=,a,b;i<=n;i++)

     {

         scanf("%d%d",&a,&b);

         if (a<) p[i].x=(frac){-a,b-w},p[i].y=(frac){-a,b+w};

         else p[i].x=(frac){a,w-b},p[i].y=(frac){a,-w-b};

         lisa[++li]=p[i].y;

     }

     sort(lisa+,lisa++li);

     for (int i=;i<=n;i++) p[i].z=lower_bound(lisa+,lisa++li,p[i].y)-lisa;

     sort(p+,p++n,cmpx);

     t.clear(n);

     LL ans=;

     for (int i=;i<=n;i++)

     {

         ans+=t.query(p[i].z);

         t.add(p[i].z,);

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

Codeforces956D. Contact ATC

最新文章

热门文章