fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define pii pair<int,int>
  6. #define f first
  7. #define s second
  8. #define all(x) x.begin(),x.end()
  9. #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  10. #define pll pair<ll,ll>
  11.  
  12. int dx[4]={0,0,1,-1};
  13. int dy[4]={1,-1,0,0};
  14.  
  15. void setIO(string s) {
  16.     freopen((s + ".in").c_str(), "r", stdin);
  17.     freopen((s + ".out").c_str(), "w", stdout);
  18. }
  19.  
  20. inline pll operator-(pll a,pll b){
  21.     return pll(a.f-b.f,a.s-b.s);
  22. }
  23.  
  24. inline ll cross(pll a,pll b){
  25.     return a.f*b.s-a.s*b.f;
  26. }
  27.  
  28. inline ll dot(pll a,pll b){
  29.     return a.f*b.f+a.s*b.s;
  30. }
  31.  
  32. inline int ori(pll a,pll b,pll c){
  33.     ll ans=cross(b-a,c-a);
  34.     return (ans==0?0:(ans<0?-1:1));
  35. }
  36.  
  37. inline bool btw(pll a,pll b,pll c){
  38.     return (ori(a,b,c)==0 and dot(a-b,c-b)<=0);
  39. }
  40.  
  41. inline bool intersect(pll a,pll b,pll c,pll d){
  42.     if(btw(a,c,b)||btw(a,d,b)||btw(c,a,d)||btw(c,b,d)) return true;
  43.     return (ori(a,b,c)*ori(a,b,d)<0 and ori(c,d,a)*ori(c,d,b)<0);
  44. }
  45.  
  46. inline bool comp(pair<pll,int> a,pair<pll,int> b){
  47.     #define is_neg(x) (x.s<0 or (x.s==0 and x.f<0))
  48.     int A=is_neg(a.f);
  49.     int B=is_neg(b.f);
  50.     if(A!=B){
  51.         return A>B;
  52.     }
  53.     int res=ori(pll(0,0),a.f,b.f);
  54.     if(res>0) return true;
  55.     else if(res<0) return false;
  56.     else return a.s<b.s;
  57. }
  58.  
  59. struct BIT{
  60.     vector<int> bit;
  61.     int n;
  62.     BIT(int _n){
  63.         n=_n;
  64.         bit.resize(n+1);
  65.     }
  66.     void update(int pos,int val){
  67.         pos++;
  68.         for(;pos<=n;pos+=(pos&-pos)){
  69.             bit[pos]+=val;
  70.         }
  71.     }
  72.     int query(int pos){
  73.         pos++;
  74.         int ans=0;
  75.         for(;pos>0;pos-=(pos&-pos)){
  76.             ans+=bit[pos];
  77.         }
  78.         return ans;
  79.     }
  80. };
  81.  
  82. int main() {_
  83.     int n,m;
  84.     cin>>n>>m;
  85.     vector<pll> a(n),b(m);
  86.     for(int i=0;i<n;i++){
  87.         cin>>a[i].f>>a[i].s;
  88.     }
  89.     for(int i=0;i<m;i++){
  90.         cin>>b[i].f>>b[i].s;
  91.     }
  92.     sort(all(b));
  93.     ll ans=0;
  94.     vector<int> ord(m);
  95.     for(int i=0;i<m;i++){
  96.         vector<pair<pll,int>> pt;
  97.         for(int j=i+1;j<m;j++){
  98.             pt.push_back({b[j]-b[i],j});
  99.         }
  100.         sort(all(pt),comp);
  101.         int sz=(int)pt.size();
  102.         BIT bit(sz);
  103.         for(int i=0;i<sz;i++){
  104.             ord[pt[i].s]=i;
  105.         }
  106.         int r=i+1;
  107.         for(int j=0;j<n-1;j++){
  108.             if(a[j].f<b[i].f) continue;;
  109.             while(r<m and b[r].f<=a[j+1].f){
  110.                 bit.update(ord[r],1);
  111.                 cout << r << ' ' ;
  112.                 r++;
  113.             }
  114.             cout << '\n';
  115.             int l=lower_bound(all(b),pll(a[j].f,-1))-b.begin();
  116.             l=max(l,i+1);
  117.             for(int k=l;k<r;k++){
  118.                 if(intersect(b[i],b[k],a[j],a[j+1])) ans++;
  119.             }
  120.             pll L=a[j]-b[i];
  121.             pll R=a[j+1]-b[i];
  122.             if(comp(make_pair(R,-1),make_pair(L,-1))) swap(L,R);
  123.             int tl=lower_bound(all(pt),make_pair(L,-1),comp)-pt.begin();
  124.             int tr=upper_bound(all(pt),make_pair(R,m),comp)-pt.begin()-1;
  125.             cout<<r << ' ' << ans << ' ' << tl <<' '<< tr <<'\n';
  126.             if(tl<=tr) ans+=(tr-tl+1)-(bit.query(tr)-bit.query(tl-1));
  127.         }
  128.         //cout<<ans<<'\n';
  129.     }
  130.     for(int i=0;i<m;i++){
  131.         int pos=-1;
  132.         for(int j=0;j<n-1;j++){
  133.             if(a[j].f<b[i].f and a[j+1].f>=b[i].f){
  134.                 pos=j;
  135.             }
  136.         }
  137.         if(pos==-1) continue;
  138.         for(int j=i+1;j<m;j++){
  139.             if(intersect(b[i],b[j],a[pos],a[pos+1])) ans++;
  140.         }
  141.     }
  142.     cout<<ans<<'\n';
  143.     return 0;
  144. }
  145. //maybe its multiset not set
  146. //yeeorz
  147. //diaoborz
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
10 18
0 0
1 91
2 7
3 27
4 99
5 93
6 38
7 30
8 54
9 43
8 75
7 86
5 10
2 22
8 69
6 83
4 88
5 99
1 38
3 78
9 69
1 30
4 17
2 78
6 65
7 42
9 32
3 76
stdout
copy 
1 2 3 
4 2 0 16
4 5 
6 16 0 2
6 7 
8 19 3 13
8 9 
10 29 11 13
10 11 
12 31 4 10
12 13 
14 36 3 3
14 15 
16 37 3 4
16 17 
18 38 4 4
2 3 
4 40 0 15
4 5 
6 54 0 2
6 7 
8 57 3 14
8 9 
10 67 11 14
10 11 
12 69 4 10
12 13 
14 74 3 3
14 15 
16 75 3 4
16 17 
18 76 4 4
3 4 5 
6 76 0 3
6 7 
8 81 4 11
8 9 
10 89 10 11
10 11 
12 91 3 9
12 13 
14 97 3 3
14 15 
16 97 3 3
16 17 
18 97 3 3
4 5 
6 97 0 -1
6 7 
8 99 0 13
8 9 
10 110 12 13
10 11 
12 112 2 12
12 13 
14 118 2 1
14 15 
16 118 2 3
16 17 
18 119 4 3
5 6 7 
8 121 0 11
8 9 
10 132 10 11
10 11 
12 134 2 9
12 13 
14 140 2 1
14 15 
16 140 2 3
16 17 
18 141 4 3
6 7 
8 143 0 11
8 9 
10 154 10 11
10 11 
12 156 2 9
12 13 
14 162 2 1
14 15 
16 162 2 3
16 17 
18 163 4 3
7 8 9 
10 164 9 10
10 11 
12 166 4 8
12 13 
14 170 2 3
14 15 
16 171 2 2
16 17 
18 171 2 2
8 9 
10 172 9 9
10 11 
12 174 1 8
12 13 
14 180 1 0
14 15 
16 180 1 3
16 17 
18 181 4 3
9 10 11 
12 184 5 8
12 13 
14 186 1 4
14 15 
16 189 1 0
16 17 
18 189 1 0
10 11 
12 189 0 -1
12 13 
14 189 0 -1
14 15 
16 189 0 3
16 17 
18 190 4 3
11 12 13 
14 190 0 -1
14 15 
16 190 0 1
16 17 
18 191 2 1
12 13 
14 191 0 -1
14 15 
16 191 0 1
16 17 
18 192 2 1
13 14 15 
16 192 0 0
16 17 
18 193 1 0
14 15 
16 193 0 -1
16 17 
18 194 0 0
15 16 17 
18 195 0 0
16 17 
18 196 0 0
198
https://ideone.com/aC8V18
language:
C++14 (gcc 8.3)
created:
332 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!