Advertisement
Guest User

Untitled

a guest
Oct 7th, 2015
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FRE(i,a,b) for(i = a; i <= b; i++)
  5. #define FRL(i,a,b) for(i = a; i < b; i++)
  6. #define mem(t, v) memset ((t) , v, sizeof(t))
  7. #define sqr(x) (x)*(x)
  8. #define all(x) x.begin(),x.end()
  9. #define un(x) x.erase(unique(all(x)), x.end())
  10. #define sf(n) scanf("%d", &n)
  11. #define sff(a,b) cin >> a >> b
  12. #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
  13. //#define D(x) cout<<#x " = "<<(x)<<endl
  14. #define pf printf
  15. #define VI vector <int>
  16. #define pii pair <int, int>
  17. #define pll pair <LL, LL>
  18. #define pb push_back
  19. #define mp make_pair
  20. #define pi acos(-1.00)
  21. //#define DBG pf("Hi\n")
  22. #define sz size()
  23. #define ins insert
  24. #define fi first
  25. #define se second
  26. #define xx x
  27. #define yy y
  28. #define inf (1<<29)
  29. #define eps 1e-10
  30.  
  31.  
  32. typedef long long int LL;
  33. typedef long double db;
  34.  
  35. /* Min Priority queue
  36. priority_queue<int, vector<int>, greater <int> > q;
  37. */
  38.  
  39. //int dx[] = {+0,+1,+0,-1};
  40. //int dy[] = {+1,+0,-1,+0};
  41. //int dx[] = {-1,-1,-1,+0,+0,+1,+1,+1};
  42. //int dy[] = {-1,+0,+1,-1,+1,-1,+0,+1};
  43. //bool check(int n, int pos) {return (bool) (n & (1<<pos));}
  44. //int on(int n, int pos) {return n | (1<<pos); }
  45. //int off(int n, int pos) {return n & ~(1<<pos); }
  46. struct point // Creates normal 2D point
  47. {
  48. double x, y;
  49. };
  50. int order(point l, point r, point mid) // (l___r) -> mid
  51. {
  52. LL ret = 0;
  53. ret += l.xx*r.yy + r.xx*mid.yy + mid.xx*l.yy - l.xx*mid.yy - mid.xx*r.yy - r.xx*l.yy;
  54. if(ret < eps && ret > -eps)
  55. return 0;
  56. if(ret < 0) return -1;
  57. if(ret > 0) return +1;
  58.  
  59. }
  60.  
  61.  
  62.  
  63. struct line // Creates a line with equation ax + by + c = 0
  64. {
  65. double a, b, c;
  66. line() {}
  67. line( point p1,point p2 )
  68. {
  69. a = p1.y - p2.y;
  70. b = p2.x - p1.x;
  71. c = p1.x * p2.y - p2.x * p1.y;
  72. }
  73. };
  74.  
  75. struct circle // Creates a circle with point 'center' as center and r as radius
  76. {
  77. point center;
  78. double r;
  79. circle() {}
  80. circle( point P, double rr )
  81. {
  82. center = P;
  83. r = rr;
  84. }
  85. };
  86.  
  87. db dist(point a, point b)
  88. {
  89. return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  90. }
  91. db dist2(point a, point b)
  92. {
  93. return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  94. }
  95.  
  96. vector <point> CLI; /// The points where the circle intersects the line.
  97.  
  98. bool eq(db a, db b)
  99. {
  100. if(fabs(a-b) <= eps)
  101. return 1;
  102. return 0;
  103. }
  104.  
  105. bool intersection(circle C,line L)
  106. {
  107. point p1, p2;
  108. double a, b, c, d, x = C.center.x, y = C.center.y;
  109. d = C.r*C.r - x*x - y*y;
  110. if( eq( L.a, 0) )
  111. {
  112. p1.y = p2.y = -L.c / L.b;
  113. a = 1;
  114. b = 2 * x;
  115. c = p1.y * p1.y - 2 * p1.y * y - d;
  116. d = b * b - 4 * a * c;
  117. d = sqrt( fabs (d) );
  118. p1.x = ( b + d ) / ( 2 * a );
  119. p2.x = ( b - d ) / ( 2 * a );
  120. }
  121. else
  122. {
  123. a = L.a *L.a + L.b * L.b;
  124. b = 2 * ( L.a * L.a * y - L.b * L.c - L.a * L.b * x);
  125. c = L.c * L.c + 2 * L.a * L.c * x - L.a * L.a * d;
  126. d = b * b - 4 * a * c;
  127. d = sqrt( fabs(d) );
  128. p1.y = ( b + d ) / ( 2 * a );
  129. p2.y = ( b - d ) / ( 2 * a );
  130. p1.x = ( -L.b * p1.y -L.c ) / L.a;
  131. p2.x = ( -L.b * p2.y -L.c ) / L.a;
  132. }
  133. CLI.pb(p1);
  134. CLI.pb(p2);
  135. return true;
  136. }
  137.  
  138. bool gre(db a, db b)
  139. {
  140. if(fabs(a - b) <= eps)
  141. return true;
  142. if(a > b + eps)
  143. return true;
  144. return false;
  145. }
  146.  
  147. bool lte(db a, db b)
  148. {
  149. if(fabs(a - b) <= eps)
  150. return true;
  151. if( a + eps < b )
  152. return true;
  153. return false;
  154. }
  155.  
  156. db Evaluate(line L, point P)
  157. {
  158. return L.a * P.x + L.b * P.y + L.c;
  159. }
  160.  
  161. point A1,B1,C1, C2;
  162. int main()
  163. {
  164. //freopen("in.txt", "r", stdin);
  165. //freopen("out.txt", "w", stdout);
  166. //ios_base::sync_with_stdio(0); cin.tie(0);
  167. int i, j, k, cs, t;
  168. sff(A1.x,A1.y);
  169. sff(B1.x,B1.y);
  170. sff(C1.x,C1.y);
  171.  
  172. line AC = line(A1,C1);
  173. circle O = circle(B1,dist(B1,C1));
  174.  
  175. intersection(O,AC);
  176. assert(CLI.sz > 0);
  177.  
  178. if( eq(dist2(B1,A1) , dist2(A1,C1) + dist2(B1,C1)))
  179. {
  180. pf("YES\n");
  181. return 0;
  182. }
  183. if(eq(CLI[0].x, C1.x) && eq(CLI[0].y, C1.y))
  184. C2 = CLI[1];
  185. else
  186. C2 = CLI[0];
  187. mnx = min(A1.x, C1.x);
  188. mxx = max(A1.x, C1.x);
  189. mny = min(A1.y, C1.y);
  190. mxy = max(A1.y, C1.y);
  191. line AB = line(A1,B1);
  192. assert(C2.x < 1000 && C2.y < 1000);
  193. if(Evaluate(AB, C2) * Evaluate(AB,C1) >= eps)
  194. {
  195. if(!order(A1,C2,B1))
  196. {
  197. pf("YES\n");
  198. return 0;
  199. }
  200. pf("NO\n");
  201. cout << setprecision(20) << A1.x << " " << A1.y << endl;
  202. cout << setprecision(20) << B1.x << " " << B1.y << endl;
  203. cout << setprecision(20) << C2.x << " " << C2.y << endl;
  204. }
  205. else
  206. pf("YES\n");
  207.  
  208. return 0;
  209. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement