fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vll;
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12.  
  13. struct punkt{
  14.     ll x, y; int ind;
  15. };
  16.  
  17. vector<punkt> v;
  18.  
  19. ll xs, xm, ys, ym;
  20. ll X, Y;
  21. int mode, t;
  22.  
  23. ll policz(ll x1, ll x2, ll y1, ll y2){
  24.     return x1 * y2 - y1 * x2;
  25. }
  26.  
  27. bool cmp(const punkt &a, const punkt &b) {
  28.     ll ax = a.x - X;
  29.     ll ay = a.y - Y;
  30.     ll bx = b.x - X;
  31.     ll by = b.y - Y;
  32.  
  33.     ll wek = policz(ax, ay, bx, by);
  34.  
  35.     if(t == 1) wek = -wek;
  36.     if(wek != 0) return wek > 0;
  37.  
  38.     ll da = ax * ax + ay * ay;
  39.     ll db = bx * bx + by * by;
  40.  
  41.     if(mode == 0) return da < db;
  42.     else return da > db;
  43. }
  44.  
  45. bool cmp2(int a, int b){
  46.     return cmp(v[a], v[b]);
  47. }
  48.  
  49. const int N = 128 * 1024;
  50. ll tree[2 * N];
  51.  
  52. void upd(int v){
  53.     v += N;
  54.     while(v){
  55.         tree[v]++;
  56.         v >>= 1;
  57.     }
  58. }
  59.  
  60. int query(int r){
  61.     int l = N;
  62.     r += N;
  63.     ll wyn = 0;
  64.     while(l <= r){
  65.         if(l & 1) wyn += tree[l++];
  66.         if(!(r & 1)) wyn += tree[r--];
  67.         l >>= 1;
  68.         r >>= 1;
  69.     }
  70.     return wyn;
  71. }
  72.  
  73. int main(){
  74.     ios_base::sync_with_stdio(0);
  75.     cin.tie(0);
  76.  
  77.     cin >> xs >> ys >> xm >> ym;
  78.  
  79.     ll dx = xm - xs, dy = ym - ys;
  80.  
  81.     int n;
  82.     cin >> n;
  83.     punkt p[n];
  84.  
  85.     ll cntl = 0, cntp = 0;
  86.     vector<punkt> pkt[2];
  87.  
  88.     for(int i = 0; i < n; i++){
  89.         ll x, y;
  90.         cin >> x >> y;
  91.         p[i] = {x, y, i};
  92.  
  93.         ll nx = x - xs, ny = y - ys;
  94.         ll w = policz(dx, nx, dy, ny);
  95.  
  96.         if(w > 0){
  97.             pkt[0].pb(p[i]);
  98.         }
  99.         else if(w == 0){
  100.             ll d = nx * dx + ny * dy;
  101.             ll dl = dx * dx + dy * dy;
  102.  
  103.             if(d < 0) cntl++;
  104.             else if(d > dl) cntp++;
  105.         }
  106.         else{
  107.             pkt[1].pb(p[i]);
  108.         }
  109.     }
  110.  
  111.     ll wyn = cntp * (cntp - 1) / 2 + cntl * (cntl - 1) / 2;
  112.  
  113.     for(t = 0; t < 2; t++){
  114.         v = pkt[t];
  115.         int m = v.size();
  116.  
  117.         if(m <= 1) continue;
  118.  
  119.         X = xs;
  120.         Y = ys;
  121.         mode = 0;
  122.         sort(v.begin(), v.end(), cmp);
  123.  
  124.         X = xm;
  125.         Y = ym;
  126.  
  127.         mode = 1;
  128.         vi kol(m);
  129.         iota(kol.begin(), kol.end(), 0);
  130.         sort(kol.begin(), kol.end(), cmp2);
  131.  
  132.         vi poz(m);
  133.         for(int i = 0; i < m; i++) poz[kol[i]] = i;
  134.  
  135.         for(int i = 0; i < m; i++){
  136.             wyn += i - query(poz[i]);
  137.             upd(poz[i]);
  138.         }
  139.  
  140.         for(int i = 0; i < 2 * N; i++) tree[i] = 0;
  141.     }
  142.  
  143.     cout << wyn << "\n";
  144.  
  145.  
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0.01s 5644KB
comments (?)
stdin
copy 
0 0 100 0
4
50 20
50 30
50 50
12 00
stdout
copy 
3
https://ideone.com/CLTXfL
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!