fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
4
https://ideone.com/FPWR0d
language:
C++ (gcc 8.3)
created:
11 years 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!