fork download
  1. #include <cstdio>
  2. #include <ctime>
  3. #include <cassert>
  4. #include <algorithm>
  5. #include <set>
  6. #include <cmath>
  7. using namespace std;
  8.  
  9. #define y1 stupid_cmath
  10. #define maxn 400010
  11.  
  12. int xc,active,ans,in_set[maxn];
  13.  
  14. struct line{
  15. int x1,y1,x2,y2,idx;
  16. double getyc(){
  17. return (double)y1+double(y2-y1)/(double)(x2-x1)*(double)(xc-x1);
  18. }
  19. bool operator<(const line&he)const{
  20. double yc1=(long double)he.y1+(long double)(he.y2-he.y1)/(long double)(he.x2-he.x1)*(long double)(xc-he.x1);
  21. double yc2=(long double)y1+(long double)(y2-y1)/(long double)(x2-x1)*(long double)(xc-x1);
  22. return yc2<yc1;
  23. }
  24. bool operator==(const line&he)const{
  25. return (idx==he.idx);
  26. }
  27. line(){}
  28. line(int x1,int y1,int x2,int y2,int idx):x1(x1),y1(y1),x2(x2),y2(y2),idx(idx){}
  29. };
  30.  
  31. struct event{
  32. line me;
  33. int time,type;
  34. bool operator<(const event&he)const{
  35. return (time<he.time||(time==he.time&&type<he.type));
  36. }
  37. event(){}
  38. event(line me,int time,int type):me(me),time(time),type(type){}
  39. };
  40.  
  41. struct treap{
  42. line key;
  43. int prior,cnt;
  44. treap*l,*r;
  45. treap(){}
  46. treap(line me,int prior):key(me),prior(prior),l(NULL),r(NULL),cnt(0){}
  47. };
  48. typedef treap * ptreap;
  49.  
  50. ptreap root;
  51.  
  52. int cnt(ptreap t){
  53. if(!t)return 0;else return t->cnt;
  54. }
  55.  
  56. void upd(ptreap&t){
  57. if(t)t->cnt=1+cnt(t->l)+cnt(t->r);
  58. }
  59.  
  60. void split(ptreap t,line key,ptreap&l,ptreap&r){
  61. if(!t){l=r=NULL;return;}
  62. if(key<t->key)split(t->l,key,l,t->l),r=t;else split(t->r,key,t->r,r),l=t;
  63. upd(t);
  64. upd(l);
  65. upd(r);
  66. }
  67.  
  68. void insert(ptreap&t,ptreap it){
  69. if(!t)t=it;else
  70. if(it->prior>t->prior)split(t,it->key,it->l,it->r),t=it;else{
  71. if(it->key<t->key)insert(t->l,it);else insert(t->r,it);
  72. }
  73. upd(t);
  74. }
  75.  
  76. void merge(ptreap&t,ptreap l,ptreap r){
  77. if(!l||!r)t=l?l:r;else
  78. if(l->prior>r->prior)merge(l->r,l->r,r),t=l;else
  79. merge(r->l,l,r->l),t=r;
  80. upd(t);
  81. }
  82.  
  83. void erase(ptreap&t,line key){
  84. if(t->key==key)merge(t,t->l,t->r);else
  85. if(t->key<key)erase(t->r,key);else erase(t->l,key);
  86. upd(t);
  87. }
  88.  
  89. int place(ptreap root,line me){
  90. if(root->key==me)return cnt(root->l);
  91. if(root->key<me)return cnt(root->l)+1+place(root->r,me);
  92. return place(root->l,me);
  93. }
  94.  
  95. int getkth(ptreap root,int k){
  96. if(k==cnt(root->l))return root->key.idx;
  97. if(k<cnt(root->l))return getkth(root->l,k);else return getkth(root->r,k-cnt(root->l)-1);
  98. }
  99.  
  100. int n,i,x1,y1,x2,y2,en,rg,q,findnext,j,old;
  101. event e[maxn];
  102. line orig[maxn];
  103.  
  104. void wt(ptreap t){
  105. if(!t)return;
  106. wt(t->l);
  107. printf("%.2lf ",t->key.getyc());
  108. wt(t->r);
  109. }
  110.  
  111. int main(){
  112. // freopen("hillwalk.in","r",stdin);
  113. // freopen("hillwalk.out","w",stdout);
  114. srand(time(NULL));
  115. scanf("%d",&n);
  116. for(i=1;i<=n;i++){
  117. scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  118. e[++en]=event(line(x1,y1,x2,y2,i),x1,i);
  119. e[++en]=event(line(x1,y1,x2,y2,i),x2,-i);
  120. orig[i]=line(x1,y1,x2,y2,i);
  121. }
  122. active=1,ans=1;
  123. sort(e+1,e+en+1);
  124. for(i=1;i<=en;i++)if(i>rg){
  125. xc=e[i].time;
  126. // wt(root);
  127. findnext=0;
  128. j=i;
  129. while(j<en&&e[j+1].time==e[i].time)++j;
  130. for(q=i;q<=j;q++)if(e[q].type>0){
  131. insert(root,new treap(e[q].me,(rand()<<15)+rand()));
  132. }else
  133. if(e[q].type==-active)findnext=1;else erase(root,e[q].me);
  134. if(findnext){
  135. old=active;
  136. in_set[active]=0;
  137. int it=place(root,orig[active]);
  138. if(it==0)break;
  139. ++ans;
  140. active=getkth(root,--it);
  141. erase(root,orig[old]);
  142. }
  143. rg=j;
  144. }
  145. printf("%d\n",ans);
  146. return 0;
  147. }
  148.  
Success #stdin #stdout 0s 23352KB
stdin
6
0 0 6 6
4 3 10 7
4 1 8 4
6 0 12 10
10 4 13 7
4 0 7 2
stdout
4