fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. struct data{
  7. 	double x,y;
  8. 	data(){}
  9. 	data(int _x,int _y): x(_x),y(_y){}
  10. 	data operator-(data a)const{return data(x - a.x , y - a.y);}
  11. 	data operator+(data a)const{return data(x + a.x , y + a.y);}
  12. 	bool operator^(data a)const{return x * a.y - y * a.x > 0;}
  13. };
  14.  
  15. int n,m,lx,ly,rx,ry;
  16. data d[7000];
  17. int a[7000],b[7000],ans[7000];
  18.  
  19. int lower(data ask){
  20. 	int l = 0,r = n+1,mid;
  21. 	while(r - l >1){
  22. 		mid  = (l+r)/2;
  23. 		if(d[mid] ^ data(ask.x - b[mid], ask.y - ry))r = mid;
  24. 		else l = mid;
  25. 	}
  26. 	return r;
  27. }
  28.  
  29. int main(){
  30. 	while(~scanf("%d",&n),n){
  31. 		scanf("%d%d%d%d%d",&m,&lx,&ly,&rx,&ry);
  32. 		for(int i= 1;i<=n;++i){
  33. 			scanf("%d%d",&a[i],&b[i]);
  34. 			d[i] = data(a[i] - b[i] , ly - ry);
  35. 		}
  36. 		a[0] = b[0] = lx;
  37. 		d[0] = data(0,ly-ry);
  38. 		a[n+1] = b[n+1] = rx;
  39. 		d[n+1] = data (0,ly - ry);
  40. 		memset(ans,0,sizeof ans);
  41. 		for(int i=0;i<m;++i){
  42. 			int x,y;
  43. 			scanf("%d%d",&x,&y);
  44. 			ans[lower(data(x,y))]++;
  45. 		}
  46. 		for(int i=1;i<=n+1;++i){
  47. 			printf("%d: %d\n",i-1,ans[i]);
  48. 		}
  49. 		puts("");
  50. 	}
  51. }
  52.  
  53.  
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gvN0dV
language:
C++ (gcc 8.3)
created:
10 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!