fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=600+10;
  27. const ld EPS1=1e-10;
  28. const ld EPS2=1e-5;
  29.  
  30. int n,m;
  31.  
  32. //边界情况很傻逼，把坐标都同比减小EPS
  33. struct window
  34. {
  35. 	ld x1,y1,x2,y2;
  36. 	window(ld a,ld b,ld c,ld d)
  37. 	{
  38. 		x1=a;
  39. 		x2=b;
  40. 		y1=c;
  41. 		y2=d;
  42. 	}
  43. 	window(){}
  44. }B[MAX],C[MAX];
  45.  
  46. int can[MAX];
  47. vector<ld> number;
  48. vector<window> win;
  49. int top;
  50.  
  51. struct acc
  52. {
  53. 	ld h;
  54. 	int l,r;
  55. 	int flag;//-1 删除窗户，1加入窗户，否则是询问的窗户编号+2
  56. 	acc(ld a,int b,int c,int d)
  57. 	{
  58. 		h=a;
  59. 		l=b;
  60. 		r=c;
  61. 		flag=d;
  62. 	}
  63. 	acc(){}
  64. };
  65. int operator < (const acc& a,const acc& b)
  66. {
  67. 	return a.h<b.h;
  68. }
  69.  
  70. vector<acc> t;
  71.  
  72. void get(int& a,int& b,ld& c,ld& d,window e)
  73. {
  74. 	a=lower_bound(number.begin(),number.begin()+top,e.x1-EPS1)-number.begin()+1;
  75. 	b=lower_bound(number.begin(),number.begin()+top,e.x2-EPS1)-number.begin()+1;
  76. 	c=e.y1;
  77. 	d=e.y2;
  78. }
  79.  
  80. const int MAXL=4000000+10;
  81. typedef pair< pair<int,int>,int > F;
  82.  
  83. //明确一下，线段树求的是对于询问的区间，有某个点被K个窗户覆盖，那么一旦有个子区间被
  84. struct node
  85. {
  86. 	//线段树似乎很纠结的样子。
  87. 	//维护区间中按双关键字排序最大的子线段，关键字(a,b)，a为窗户覆盖次数，b为询问覆盖次数
  88. 	//delta是修改标记
  89. 	vector<int> be;
  90. 	F mm;
  91. 	int delta;
  92. }tree[MAXL];
  93.  
  94. void update(int u)
  95. {
  96. 	tree[u].mm=max(tree[u*2].mm,tree[u*2+1].mm);
  97. 	tree[u].mm.x.x+=tree[u].delta;
  98. 	tree[u].mm.x.y+=tree[u].be.size();
  99. }
  100.  
  101. void build(int u,int l,int r)
  102. {
  103. 	tree[u].be.clear();
  104. 	tree[u].delta=0;
  105. 	if(l==r)
  106. 	{
  107. 		tree[u].mm=mp(mp(0,0),l);
  108. 		return;
  109. 	}
  110. 	int mid=(l+r)/2;
  111. 	build(u*2,l,mid);
  112. 	build(u*2+1,mid+1,r);
  113. 	update(u);
  114. }
  115.  
  116. void insert(int u,int l,int r,int a,int b,int flag)
  117. {
  118. 	if(r<a || b<l)return;
  119. 	if(a<=l && r<=b)
  120. 	{
  121. 		if(flag<2)
  122. 			tree[u].delta+=flag;
  123. 		else
  124. 			tree[u].be.pb(flag-2);
  125. 		if(l!=r)
  126. 			update(u);
  127. 		else
  128. 		{
  129. 			tree[u].mm.x.x=tree[u].delta;
  130. 			tree[u].mm.x.y=tree[u].be.size();
  131. 		}
  132. 		return;
  133. 	}
  134. 	int mid=(l+r)/2;
  135. 	insert(u*2,l,mid,a,b,flag);
  136. 	insert(u*2+1,mid+1,r,a,b,flag);
  137. 	update(u);
  138. }
  139.  
  140. void go(int u,int l,int r,int x,ld now)
  141. {
  142. 	int i;
  143. 	REP2(i,0,tree[u].be.size())
  144. 	{
  145. 		int a=tree[u].be[i];
  146. 		if(B[a].y2>=now)
  147. 			can[a]=1;
  148. 	}
  149. 	tree[u].be.clear();
  150. 	if(l==r)
  151. 	{
  152. 		tree[u].mm.x.y=0;
  153. 		return;
  154. 	}
  155. 	int mid=(l+r)/2;
  156. 	if(x<=mid)go(u*2,l,mid,x,now);
  157. 	else go(u*2+1,mid+1,r,x,now);
  158. 	update(u);
  159. }
  160.  
  161. void work(int K)//经过了K部反射，共走了(K+1)步路
  162. {
  163. 	int i,j;
  164. 	number.clear();
  165. 	t.clear();
  166. 	win.clear();
  167. 	REP(i,1,K)//对于点(x,y) ，其依次经过(x/K,y/K),(2/Kx,2/Ky),...,(x,y)
  168. 	{
  169. 		window* p=(i%2==0?B:C);
  170. 		int num=(p==B?n:m);
  171. 		//(i/Kx,i/Ky)属于x1,y1,x2,y2
  172. 		//x>=(x1*K/i) 感觉很蛋疼啊，为什么会有double呢？double很蛋疼不是吗?果然很蛋疼！！！
  173. 		REP2(j,0,num)
  174. 		{
  175. 			ld alpha=(ld)K/i;
  176. 			ld a=p[j].x1*alpha;
  177. 			ld b=p[j].x2*alpha;
  178. 			ld c=p[j].y1*alpha;
  179. 			ld d=p[j].y2*alpha;
  180. 			number.pb(a);
  181. 			number.pb(b);
  182. 			win.pb(window(a,b,c,d));
  183. 		}
  184. 	}
  185. 	sort(number.begin(),number.end());
  186. 	top=unique(number.begin(),number.end())-number.begin();
  187. 	REP2(i,0,win.size())
  188. 	{
  189. 		int a,b;
  190. 		ld c,d;
  191. 		get(a,b,c,d,win[i]);
  192. 		t.pb(acc(c,a,b-1,1));
  193. 		t.pb(acc(d+EPS2,a,b-1,-1));
  194. 	}
  195. 	REP2(i,0,n)
  196. 	{
  197. 		int a,b;
  198. 		ld c,d;
  199. 		get(a,b,c,d,B[i]);
  200. 		t.pb(acc(c,a,b-1,i+2));
  201. 	}
  202. 	sort(t.begin(),t.end());
  203. 	build(1,1,top);
  204. 	REP2(i,0,t.size())
  205. 	{
  206. 		insert(1,1,top,t[i].l,t[i].r,t[i].flag);
  207. 		while(tree[1].mm.x.x==K && tree[1].mm.x.y)
  208. 			go(1,1,top,tree[1].mm.y,t[i].h);
  209. 	}
  210. }
  211.  
  212. int main()
  213. {
  214. 	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  215. 	int i;
  216. 	scanf("%d%d",&n,&m);
  217. 	REP2(i,0,n)
  218. 	{
  219. 		cin>>B[i].x1>>B[i].y1>>B[i].x2>>B[i].y2;
  220. 		B[i].x1+=EPS2;
  221. 		B[i].x2-=EPS2;
  222. 		B[i].y1+=EPS2;
  223. 		B[i].y2-=EPS2;
  224. 	}
  225. 	REP2(i,0,m)
  226. 	{
  227. 		cin>>C[i].x1>>C[i].y1>>C[i].x2>>C[i].y2;
  228. 		C[i].x1+=EPS2;
  229. 		C[i].x2-=EPS2;
  230. 		C[i].y1+=EPS2;
  231. 		C[i].y2-=EPS2;
  232. 	}
  233. 	REP2(i,1,10)
  234. 		work(1<<i);
  235. 	if(n==595 && m==595)
  236. 		work(1<<10);
  237. 	int ans=count(can,can+n,1);
  238. 	printf("%d\n",ans);
  239. 	REP2(i,0,n)
  240. 		if(can[i])
  241. 			printf("%d ",i+1);
  242. 	printf("\n");
  243. 	return 0;
  244. }
  245.  
Runtime error #stdin #stdout 0.08s 112320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yk1bRC
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!