fork(1) 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.                 r++;
  112.             }
  113.             int l=lower_bound(all(b),pll(a[j].f,-1))-b.begin();
  114.             l=max(l,i+1);
  115.             for(int k=l;k<r;k++){
  116.                 if(intersect(b[i],b[k],a[j],a[j+1])) ans++;
  117.             }
  118.             pll L=a[j]-b[i];
  119.             pll R=a[j+1]-b[i];
  120.             if(comp(make_pair(R,-1),make_pair(L,-1))) swap(L,R);
  121.             int tl=lower_bound(all(pt),make_pair(L,-1),comp)-pt.begin();
  122.             int tr=upper_bound(all(pt),make_pair(R,m),comp)-pt.begin()-1;
  123.             //cout<<i<<' '<<j<<' '<<tl<<' '<<tr<<'\n';
  124.             if(tl<=tr) ans+=(tr-tl+1)-(bit.query(tr)-bit.query(tl-1));
  125.         }
  126.         //cout<<ans<<'\n';
  127.     }
  128.     for(int i=0;i<m;i++){
  129.         int pos=-1;
  130.         for(int j=0;j<n-1;j++){
  131.             if(a[j].f<b[i].f and a[j+1].f>=b[i].f){
  132.                 pos=j;
  133.             }
  134.         }
  135.         if(pos==-1) continue;
  136.         for(int j=i+1;j<m;j++){
  137.             //if(intersect(b[i],b[j],a[pos],a[pos+1])) ans++;
  138.         }
  139.     }
  140.     cout<<ans<<'\n';
  141.     return 0;
  142. }
  143. //maybe its multiset not set
  144. //yeeorz
  145. //diaoborz
Success #stdin #stdout 0.01s 5224KB
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 
196
https://ideone.com/xmX5zT
language:
C++14 (gcc 8.3)
created:
18 hours 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!