API tools faq
paste
_no0B

zahin_geo

_no0B
Apr 25th, 2019
116
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.68 KB | None | 0 0
raw download clone embed print report
  1. #include <ext/rope>
  2. #include <bits/stdtr1c++.h>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_cxx;
  6. using namespace __gnu_pbds;
  7. using namespace namespace;
  8. #define clr(ar) memset(ar, 0, sizeof(ar))
  9. #define read() freopen("lol.txt", "r", stdin)
  10. #define ran(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a))
  11. #define dbg(x) cout << #x << " = " << x << endl
  12. /// Point In Polygon
  13. #define MAX 100010
  14. struct Point{
  15.     long long x, y;
  16.     Point(){
  17.     }
  18.     Point(long long xi, long long yi){
  19.         x = xi, y = yi;
  20.     }
  21. };
  22. struct Segment{
  23.     struct Point P1, P2;
  24.     Segment(){
  25.     }
  26.     Segment(struct Point P1i, struct Point P2i){
  27.         P1 = P1i, P2 = P2i;
  28.     }
  29. };
  30. /// Returns 0 if ABC is collinear, positive if ABC is a left turn, negative if ABC is a right turn
  31. long long ccw(struct Point A, struct Point B, struct Point C){
  32.     return ((B.x - A.x) * (C.y - A.y)) - ((C.x - A.x) * (B.y - A.y));
  33. }
  34. /// Returns true if Point P lies on the Segment (both end-points inclusive)
  35. bool PointOnSeg(struct Segment S, struct Point P){
  36.     long long x = P.x, y = P.y, x1 = S.P1.x, y1 = S.P1.y, x2 = S.P2.x, y2 = S.P2.y;
  37.     long long a = x - x1, b = y - y1, c = x2 - x1, d = y2 - y1, dot = (a * c) + (b * d), len = (c * c) + (d * d);
  38.     if (x1 == x2 && y1 == y2) return (x1 == x && y1 == y);
  39.     if (dot < 0 || dot > len) return false;
  40.     return ((((x1 * len) + (dot * c)) == (x * len)) && (((y1 * len) + (dot * d)) == (y * len)));
  41. }
  42. struct Polygon{
  43.     #define CLOCKWISE 11230926
  44.     #define ANTICLOCK 37281927
  45.     int n; /// n should be greater than 1
  46.     struct Point ar[MAX]; /// Points in polygon in clockwise order
  47.     Polygon(){
  48.     }
  49.     /// Points in T are either in anti-clockwise or clockwise order
  50.     Polygon(int ni, struct Point* T, int flag){
  51.         n = ni;
  52.         for (int i = 0; i < n; i++){
  53.             if (flag == CLOCKWISE) ar[i] = T[i];
  54.             else ar[i] = T[n - i - 1];
  55.         }
  56.     }
  57.     /// strictly should be true if P needs to be strictly contained in the polygon
  58.     bool contains(struct Point P, bool strictly){
  59.         int mid, low = 1, high = n - 1, idx = 1;
  60.         while (low <= high){
  61.             mid = (low + high) >> 1;
  62.             if (ccw(ar[0], P, ar[mid]) > 0) low = mid + 1;
  63.             else idx = mid, high = mid - 1;
  64.         }
  65.         if (!strictly && PointOnSeg(Segment(ar[0], ar[n - 1]), P)) return true;
  66.         if (!strictly && PointOnSeg(Segment(ar[idx], ar[idx - 1]), P)) return true;
  67.         if (idx == 1 || ccw(ar[0], P, ar[n - 1]) == 0) return false;
  68.         return (ccw(ar[idx], P, ar[idx - 1]) < 0);
  69.     }
  70. };
  71.  
  72.  
  73.  
  74. /// Point Rotations
  75. struct Point{
  76.     double x, y;
  77.     Point(){
  78.     }
  79.     Point(double xi, double yi){
  80.         x = xi, y = yi;
  81.     }
  82. };
  83. double dis(struct Point A, struct Point B){
  84.     double x = A.x - B.x;
  85.     double y = A.y - B.y;
  86.     return sqrt((x * x) + (y * y));
  87. }
  88. /// Rotate P anti-clockwise around the centre point by theta (theta in degrees)
  89. struct Point rotate(struct Point centre, struct Point P, double theta){
  90.     P.x -= centre.x, P.y -= centre.y;
  91.     theta = (theta * 2.0 * acos(0.0)) / 180.0;
  92.     double s = sin(theta), c = cos(theta);
  93.     double x = (P.x * c) - (P.y * s);
  94.     double y = (P.x * s) + (P.y * c);
  95.     return Point(x + centre.x, y + centre.y);
  96. }
  97. /// Clockwise rotation from vector A to vector B
  98. double thetaX(struct Point A, struct Point B){
  99.     double dot = (B.x * A.x) + (B.y * A.y);
  100.     double det = (B.x * A.y) - (B.y * A.x);
  101.     double theta = (atan2(det, dot) * 180.0) / (2.0 * acos(0.0));
  102.     if (theta < 0) theta += 360.0;
  103.     return theta;
  104. }
  105.  
  106.  
  107.  
  108. /// Simple Polygon From Points
  109. struct Point{
  110.     int idx, x, y, d;
  111.     double theta;
  112. };
  113. int n;
  114. struct Point ar[2010];
  115. double centre_x, centre_y;
  116. int compare(const void* a, const void* b){
  117.     struct Point P1 = *(struct Point*)a;
  118.     struct Point P2 = *(struct Point*)b;
  119.     if (fabs(P1.theta - P2.theta) <= 1e-9){
  120.         double d1 = ((centre_x - P1.x) * (centre_x - P1.x)) + ((centre_y - P1.y) + (centre_y - P1.y));
  121.         double d2 = ((centre_x - P2.x) * (centre_x - P2.x)) + ((centre_y - P2.y) + (centre_y - P2.y));
  122.         if (fabs(d1 - d2) <= 1e-9) return 0;
  123.         else if (d1 < d2) return -1;
  124.         else return +1;
  125.     }
  126.     else if (P1.theta < P2.theta) return +1;
  127.     else return -1;
  128. }
  129. int main(){
  130.     int t, line, i, j;
  131.     scanf("%d", &t);
  132.     for (line = 1; line <= t; line++){
  133.         scanf("%d", &n);
  134.         centre_x = 0.0, centre_y = 0.0;
  135.         for (i = 0; i < n; i++){
  136.             scanf("%d %d", &ar[i].x, &ar[i].y);
  137.             ar[i].idx = i;
  138.             centre_x += ar[i].x;
  139.             centre_y += ar[i].y;
  140.         }
  141.         centre_x /= (1.0 * n), centre_y /= (1.0 * n);
  142.         for (i = 0; i < n; i++) ar[i].theta = atan2((double)ar[i].y - centre_y, (double)ar[i].x - centre_x);
  143.         qsort(ar, n, sizeof(struct Point), compare);
  144.         for (i = 0; i < n; i++){
  145.             if (i != 0) putchar(32);
  146.             printf("%d", ar[i].idx);
  147.         }
  148.         puts("");
  149.     }
  150.     return 0;
  151. }
  152.  
  153.  
  154.  
  155. /// Convex Hull
  156. using namespace std;
  157. struct Point {
  158.     long long x, y; /// x*x or y*y should fit long long because of cross() function
  159.     Point(){}
  160.     Point(long long a, long long b){
  161.         x = a, y = b;
  162.     }
  163.     inline bool operator < (const Point &p) const {
  164.         return ((x < p.x) || (x == p.x && y < p.y));
  165.     }
  166. };
  167. long long cross(const Point &O, const Point &A, const Point &B){
  168.     return ((A.x - O.x) * (B.y - O.y)) - ((A.y - O.y) * (B.x - O.x));
  169. }
  170. bool isConvex(vector <Point> P){ /// Polygon P convex or not, P is given in clock-wise of anti-clockwise order
  171.     int n = P.size();
  172.     ///sort(P.begin(), P.end());
  173.     if (n <= 2) return false; /// Line or point is not convex
  174.     n++, P.push_back(P[0]); /// Last point = first point
  175.     bool flag = (cross(P[0], P[1], P[2]) > 0);
  176.     for (int i = 1; (i + 1) < n; i++){
  177.         bool cmp = (cross(P[i], P[i + 1], (i + 2) == n ? P[1] : P[i + 2]) > 0);
  178.         if (cmp ^ flag) return false;
  179.     }
  180.  
  181.     return true;
  182. }
  183. /// Convex hull using the monotone chain algorithm
  184. vector <Point> convex_hull (vector<Point> P){
  185.     int i, t, k = 0, n = P.size();
  186.     vector<Point> H(n << 1);
  187.     sort(P.begin(), P.end()); /// Can be converted to O(n) using radix sort
  188.     for (i = 0; i < n; i++) {
  189.         while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
  190.         H[k++] = P[i];
  191.     }
  192.     for (i = n - 2, t = k + 1; i >= 0; i--) {
  193.         while (k >= t && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
  194.         H[k++] = P[i];
  195.     }
  196.     H.resize(k - 1); /// The last point is the same as the first in this implementation
  197.     return H;
  198. }
  199.  
  200.  
  201.  
  202. /// Circle Circle Intersection Area
  203. #define sqr(x) ((x) * (x))
  204. struct Point{
  205.     double x, y;
  206.     Point() {
  207.     }
  208.     Point(double a, double b){
  209.         x = a, y = b;
  210.     }
  211. };
  212. struct Circle{
  213.     Point centre;
  214.     double radius;
  215.     Circle(){
  216.     }
  217.     Circle(double a, double b, double c){
  218.         radius = c;
  219.         centre = Point(a, b);
  220.     }
  221.     Circle(struct Point c, double r){
  222.         centre = c;
  223.         radius = r;
  224.     }
  225. };
  226. const double pi = 2.0 * acos(0.0);
  227. double dis(Point A, Point B){
  228.     double x = (A.x - B.x);
  229.     double y = (A.y - B.y);
  230.     double res = sqrt((x * x) + (y * y));
  231.     return res;
  232. }
  233. double Area(Circle C){
  234.     return (pi * sqr(C.radius));
  235. }
  236. double intersection(Circle A, Circle B){
  237.     double x = A.radius + B.radius;
  238.     double y = dis(A.centre, B.centre);
  239.     if ((fabs(x - y) <= 1e-8) || (y > x)) return 0.0;
  240.     double c = y;
  241.     double x0 = A.centre.x, y0 = A.centre.y, r0 = A.radius;
  242.     double x1 = B.centre.x, y1 = B.centre.y, r1 = B.radius;
  243.     x = (sqr(r1) + sqr(c) - sqr(r0)) / (2.0 * r1 * c);
  244.     double CBD = acos(x) * 2.0;
  245.     y = (sqr(r0) + sqr(c) - sqr(r1)) / (2.0 * r0 * c);
  246.     double CAD = acos(y) * 2.0;
  247.     double res = (0.5 * CBD * sqr(r1)) - (0.5 * sqr(r1) * sin(CBD)) + (0.5 * CAD * sqr(r0)) - (0.5 * sqr(r0) * sin(CAD));
  248.     return res;
  249. }
  250. bool Inside(Circle A, Circle B){
  251.     double x = dis(A.centre, B.centre) + B.radius;
  252.     if ((fabs(x - A.radius) <= 1e-8) || (x < A.radius)) return true;
  253.     return false;
  254. }
  255. int main(){
  256.     double res;
  257.     int T = 0, t, i, a, b, c;
  258.     scanf("%d", &t);
  259.     while (t--){
  260.         scanf("%d %d %d", &a, &b, &c);
  261.         Circle grass = Circle(a, b, c);
  262.         scanf("%d %d %d", &a, &b, &c);
  263.         Circle wolf = Circle(a, b, c);
  264.         if (Inside(wolf, grass)) res = 0.0;
  265.         else if (Inside(grass, wolf)) res = Area(grass) - Area(wolf);
  266.         else{
  267.             res = Area(grass) - intersection(grass, wolf);
  268.         }
  269.         printf("Case #%d: %0.12f\n", ++T, res + 1e-15);
  270.     }
  271.     return 0;
  272. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!