fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define ld long double
  5. #define pb push_back
  6. #define sz size
  7. #define sc(a) scanf("%d",&a)
  8. #define scll(a) scanf("%lld",&a)
  9. #define scc(a) scanf(" %c",&a)
  10. #define scs(a) scanf(" %s",a)
  11. #define me(a,b) memset(a,b,sizeof a)
  12. #define all(a) a.begin(),a.end()
  13. #define allr(a,n) a,a+n
  14. #define loop(a,s,e) for(ll a=s;a<=e;a++)
  15. #define read_arr(a,s,n) for(int i=s;i<n+s;i++){sc(a[i]);}
  16. #define read_arr_ll(a,s,n) for(int i=s;i<n+s;i++){scll(a[i]);}
  17. #define err(a,s) cerr<<a<<s;
  18. #define err_arr(a,s,n) for(int i=s;i<n+s;i++){cerr<<a[i]<<" ";}cerr<<endl;
  19. #define F first
  20. #define S second
  21. #define ld long double
  22. #define ll long long
  23. #define pb push_back
  24. #define sz size
  25. using namespace std;
  26. const double eps = 1e-10;
  27. const double pi = acos(-1);
  28.  
  29. struct point{
  30.     double x,y;
  31.     point(){}
  32.     point(double a,double b){ x=a;y=b; }
  33.     void in(){ scanf("%lf %lf",&x,&y); }
  34.     void out(){ printf("{%.9f,%.9f}\n",x,y); }
  35.     double len(){ return hypot(x,y); }
  36.     double len2(){ return x*x+y*y; }
  37.     double angle(){ return atan2(y,x); }
  38.     point operator+(point s){ return point(s.x+x,s.y+y); }
  39.     point operator-(point s){ return point(-s.x+x,-s.y+y); }
  40.     point operator*(double k){ return point(x*k,y*k); }
  41.     point operator/(double k){ return point(x/k,y/k); }
  42.     point  norm(){ return point(x/len(),y/len()); }
  43.  
  44. };
  45.  
  46. point vec(point a,point b){ return b-a; }
  47. double dot(point a,point b){ return a.x*b.x + a.y*b.y; }
  48. double crs(point a,point b){ return a.x*b.y - a.y*b.x; }
  49.  
  50. bool same(point a,point b){
  51.     return fabs( vec(a,b).len() ) <= eps;
  52. }
  53.  
  54. // compare 2 real numbers a & b
  55. // return +1 if a > b
  56. // return  0 if a = b
  57. // return -1 if a < b
  58. int cmp(double a,double b){
  59. if( fabs(a-b) < eps )return 0;
  60. if( a-b > eps )return 1;
  61. return -1;
  62. }
  63. point rot(point p,double t){
  64.     return point( p.x*cos(t) - p.y*sin(t) , p.x*sin(t) + p.y*cos(t) );
  65. }
  66.  
  67. point rotAboutPoint(point p,double t,point q){
  68.     return q+rot(p-q,t);
  69. }
  70.  
  71. bool cmp1(point a,point b){
  72.     return cmp(a.x,b.x)==-1 ||( cmp(a.x,b.x)==0 && cmp(a.y,b.y)==-1 );
  73. }
  74.  
  75. vector<point> convexHull(vector<point>pol){
  76. sort(pol.begin(),pol.end(),cmp1);
  77.  
  78. // remove duplicate points
  79. vector<point>tmp;
  80. tmp.push_back(pol[0]);
  81. int N = pol.size();
  82. for(int i=1;i<N;i++)
  83.     if( !same(pol[i-1],pol[i]) )
  84.         tmp.push_back(pol[i]);
  85. pol=tmp;
  86.  
  87. N=pol.size();// again
  88. vector<point>up,dn;
  89. for(int i=0;i<N;i++){
  90.         while( dn.size() >=2 && crs(vec(dn[dn.size()-2],dn[dn.size()-1]),vec(dn[dn.size()-1],pol[i])) <0 )
  91.             dn.pop_back();
  92.     dn.push_back(pol[i]);
  93.     }
  94.  
  95.  
  96. for(int i=N-1;i>=0;i--){
  97.         while( up.size() >=2 && crs(vec(up[up.size()-2],up[up.size()-1]),vec(up[up.size()-1],pol[i])) <0 )
  98.             up.pop_back();
  99.     up.push_back(pol[i]);
  100.     }
  101.  
  102. dn.pop_back();
  103. up.pop_back();
  104.  
  105. vector<point>cvx;
  106. for(auto p:dn)cvx.push_back(p);
  107. for(auto p:up)cvx.push_back(p);
  108. return cvx;
  109. }
  110. /////////////////////////////////////////////////////////////////////////////
  111. bool PointInsidePolygon(const point &P, const vector<point> &poly){
  112.     int n = poly.size();
  113.     bool in = 0;
  114.  
  115.     for(int i = 0,j = n - 1;i < n;j = i++){
  116.         double dx = poly[j].x - poly[i].x;
  117.         double dy = poly[j].y - poly[i].y;
  118.  
  119.         if((poly[i].y <= P.y + eps && P.y < poly[j].y) ||
  120.             (poly[j].y <= P.y + eps && P.y < poly[i].y))
  121.             if(P.x - eps < dx * (P.y-poly[i].y) / dy+poly[i].x)
  122.                 in ^= 1;
  123.     }
  124.  
  125.     return in;
  126. }
  127. /////////////////////////////////////////////////////////////////////////////
  128. vector<point> all,ch,cn;
  129. void solve(int t){
  130. 	int n,m;
  131. 	sc(n);sc(m);
  132. 	all.clear();
  133. 	ch.clear();
  134. 	cn.clear();
  135.     loop(i,1,n){
  136. 		point tmp;
  137. 		tmp.in();
  138. 		all.pb(tmp);
  139.  
  140. 	}
  141. 	 loop(i,1,m){
  142. 		point tmp;
  143. 		tmp.in();
  144. 		ch.pb(tmp);
  145. 	}
  146. 	cn=convexHull(all);
  147. 	printf("Case %d\n",t);
  148. 	for(auto p:cn){
  149. 	   printf("%d %d\n",(int)p.x,(int)p.y); 
  150. 	}
  151. 	printf("%d %d\n",(int)cn[0].x,(int)cn[0].y);
  152. 	for(auto p:ch){
  153. 		bool ans=PointInsidePolygon(p,cn);
  154. 		printf("%d %d ",(int)p.x,(int)p.y);  
  155. 		if(ans){printf("is unsafe!\n");}
  156. 		else{printf("is safe!\n");}
  157. 	}
  158. }
  159. int main() {
  160. int t;
  161. sc(t);
  162. loop(i,1,t){
  163. solve(i);
  164. if(i<t){printf("\n");}	
  165. }
  166.  
  167. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1Zd10c
language:
C++14 (gcc 8.3)
created:
5 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!