fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for(int i=(a);i<(n);i++)
  4. #define per(i,a,n) for(int i=(n)-1;i>=(a);i--)
  5. #define mp make_pair
  6. #define pb push_back
  7.  
  8. typedef double db;
  9.  
  10. const db EPS = 1e-8;
  11. const db INF = 1e100;
  12.  
  13. inline int sign(db x, db E = EPS){return x<-E?-1:x>E;}
  14.  
  15. inline int cmp(db a,db b,db E = EPS){return sign(a-b, E);}
  16.  
  17. struct P{
  18. 	db x,y;
  19. 	P operator+(P o){return {x+o.x,y+o.y};}
  20. 	P operator-(P o){return {x-o.x,y-o.y};}
  21. 	P operator-(){ return {-x,-y}; }
  22. 	db det(P o){return x*o.y-y*o.x;}
  23. 	db dot(P o){return x*o.x+y*o.y;}
  24.     P operator*(db d) { return {x * d, y * d}; }
  25.     P operator/(db d) { return {x / d, y / d}; }
  26.  
  27. 	bool operator<(P o) const { return cmp(x,o.x) != 0? cmp(x,o.x) == -1 : cmp(y,o.y) == -1; }
  28. 	bool operator>(P o) const { return cmp(x,o.x) != 0? cmp(x,o.x) == 1 : cmp(y,o.y) == 1; }
  29.  
  30. 	bool operator==(P o){ return cmp(x,o.x) == 0 && cmp(y,o.y) == 0; }
  31.  
  32. 	void read(){
  33. 		scanf("%lf%lf",&x,&y);
  34. 	}
  35.     db abs() { return sqrt(abs2());}
  36.     db abs2() { return x * x + y * y; }
  37.     P rot90() { return {-y,x};}
  38.     P unit() { return *this/abs(); }
  39. }O = (P){0,0};
  40.  
  41. #define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
  42. #define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
  43.  
  44. P isLL(P p1, P p2, P q1, P q2) {
  45.     db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
  46.     return (p1 * a2 + p2 * a1) / (a1 + a2);
  47. }
  48.  
  49. vector<P> convexHull(vector<P> ps) {
  50.     int n = ps.size(); if(n <= 1) return ps;
  51.     sort(ps.begin(), ps.end());
  52.     vector<P> qs(n * 2); int k = 0;
  53.     for (int i = 0; i < n; qs[k++] = ps[i++]) 
  54.         while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
  55.     for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
  56.         while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
  57.     qs.resize(k - 1);
  58.     return qs;
  59. }
  60.  
  61. struct CH{
  62. 	int n;
  63.  
  64. 	vector<P> ps, lower, upper;
  65.  
  66. 	P operator[](int i){return ps[i];}
  67.  
  68. 	int find(vector<P>&vec, P dir){
  69. 		int l=0,r=vec.size();
  70. 		while(l+5<r){
  71. 			int L = (l*2+r)/3, R = (l+r*2)/3;
  72. 			if(vec[L].dot(dir) > vec[R].dot(dir))
  73. 				r=R;
  74. 			else
  75. 				l=L;
  76. 		}
  77. 		int ret = l; rep(k,l+1,r) if(vec[k].dot(dir) > vec[ret].dot(dir)) ret = k;
  78. 		return ret;
  79. 	}
  80.  
  81. 	/*
  82. 	ps[0] must be the smallest one!
  83. 	*/
  84.  
  85. 	void init(vector<P> _ps){
  86. 		ps = _ps; n = ps.size();
  87.  
  88. 		rotate(ps.begin(),min_element(ps.begin(), ps.end()),ps.end());
  89.  
  90. 		int at = max_element(ps.begin(), ps.end()) - ps.begin();
  91.  
  92. 		lower = vector<P>(ps.begin(),ps.begin() + at + 1);
  93.  
  94. 		upper = vector<P>(ps.begin()+at,ps.end()); upper.pb(ps[0]);
  95. 	}
  96.  
  97. 	int findFarest(P dir){
  98. 		if(dir.y > 0 || dir.y==0 && dir.x > 0){
  99. 			return ( (int)lower.size() -1 + find(upper,dir)) % n;
  100. 		} else {
  101. 			return find(lower,dir);
  102. 		}
  103. 	}
  104.  
  105. 	P get(int l,int r,P p1,P p2){
  106. 		int sl = crossOp(p1,p2,ps[l%n]);
  107. 		while(l+1<r){
  108. 			int m = (l+r)>>1;
  109. 			if(crossOp(p1,p2,ps[m%n]) == sl) 
  110. 				l = m;
  111. 			else
  112. 				r = m;
  113. 		}
  114.  
  115. 		return isLL(p1,p2,ps[l%n],ps[(l+1)%n]);
  116. 	}
  117.  
  118. 	vector<P> getIS(P p1,P p2){
  119. 		int X = findFarest((p2-p1).rot90());
  120. 		int Y = findFarest((p1-p2).rot90());
  121. 		if(X > Y) swap(X,Y);
  122. 		if(crossOp(p1,p2,ps[X]) * crossOp(p1,p2,ps[Y]) < 0){
  123. 			return {get(X,Y,p1,p2),get(Y,X+n,p1,p2)};
  124. 		} else {
  125. 			return {};
  126. 		}
  127. 	}
  128.  
  129. 	void update_tangent(P p, int id, int&a,int&b){
  130. 		if(crossOp(p,ps[a],ps[id]) > 0) a = id;
  131. 		if(crossOp(p,ps[b],ps[id]) < 0) b = id;
  132. 	}
  133.  
  134. 	void binary_search(int l,int r,P p,int&a,int&b){
  135. 		if(l==r) return;
  136. 		update_tangent(p,l%n,a,b);
  137. 		int sl = crossOp(p,ps[l%n],ps[(l+1)%n]);
  138. 		while(l+1<r){
  139. 			int m = l+r>>1;
  140. 			if(crossOp(p,ps[m%n],ps[(m+1)%n]) == sl)
  141. 				l=m;
  142. 			else
  143. 				r=m;
  144. 		}
  145. 		update_tangent(p,r%n,a,b);
  146. 	}
  147.  
  148. 	bool contain(P p){
  149. 		if(p.x < lower[0].x || p.x > lower.back().x) return 0;
  150. 		int id = lower_bound(lower.begin(), lower.end(),(P){p.x,-INF}) - lower.begin();
  151. 		if(lower[id].x == p.x){ 
  152. 			if(lower[id].y > p.y) return 0;	
  153. 		} else { 
  154. 			if(crossOp(lower[id-1],lower[id],p) < 0) return 0; 
  155. 		}
  156. 		id = lower_bound(upper.begin(), upper.end(),(P){p.x,INF},greater<P>()) - upper.begin();
  157. 		if(upper[id].x == p.x){
  158. 			if(upper[id].y < p.y) return 0;
  159. 		} else {
  160. 			if(crossOp(upper[id-1],upper[id],p) < 0) return 0;
  161. 		}
  162. 		return 1;
  163. 	}
  164.  
  165. 	bool get_tangent(P p,int&a,int&b){ // b->a
  166. 		if(contain(p)) return 0;
  167. 		a=b=0;
  168. 		int id = lower_bound(lower.begin(), lower.end(),p) - lower.begin();
  169. 		binary_search(0,id,p,a,b);
  170. 		binary_search(id,lower.size(),p,a,b);
  171. 		id = lower_bound(upper.begin(), upper.end(),p,greater<P>()) - upper.begin();
  172. 		binary_search((int)lower.size() - 1, (int) lower.size() - 1 + id,p,a,b);
  173. 		binary_search((int) lower.size() - 1 + id,(int) lower.size() - 1 + upper.size(),p,a,b);
  174. 		return 1;
  175. 	}
  176. };
  177.  
  178. int main(){
  179. 	return 0;
  180. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/cqUxSF
language:
C++14 (gcc 8.3)
created:
8 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!