fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using db = double;
  5.  
  6. inline void out(db x){
  7.     cout << fixed << setprecision(4) << x << "\n";
  8. }
  9.  
  10. struct Point {
  11.     db x, y;
  12.  
  13.     Point (){
  14.         x = 0;
  15.         y = 0;
  16.     }
  17.  
  18.     Point(db _x, db _y) : x(_x), y(_y) {}
  19.  
  20.     bool operator < (const Point &oth) const {
  21.         return (x < oth.x || (x == oth.x && y < oth.y));
  22.     }
  23.  
  24.     bool operator > (const Point &oth) const {
  25.         return (x > oth.x || (x == oth.x && y > oth.y));
  26.     }
  27.  
  28.     bool operator == (const Point &oth) const {
  29.         return (x == oth.x && y == oth.y);
  30.     }
  31.  
  32.     bool operator != (const Point &oth) const {
  33.         return (x != oth.x || y != oth.y);
  34.     }
  35. };
  36.  
  37. struct Line {
  38.     Point x, y;
  39.  
  40.     Line (Point _x, Point _y) : x(_x), y(_y) {}
  41. };
  42.  
  43. db cross (Point &A, Point &B, Point &C){
  44.     return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
  45. }
  46.  
  47. db dot (Point &A, Point &B, Point &C){
  48.     return (B.x - A.x) * (C.x - A.x) + (B.y - A.y) * (C.y - A.y);
  49. }
  50.  
  51. bool ccw (Point &A, Point &B, Point &C){
  52.     return (cross(A, B, C) > 0);
  53. }
  54.  
  55. vector<Point> ConvexHull (vector<Point> a){
  56.     vector<Point> hull;
  57.     sort(a.begin(), a.end());
  58.     hull.push_back(a[0]);
  59.     for (int i = 1; i < a.size(); ++i){
  60.         while (hull.size() > 1 && ccw(hull[hull.size() - 2], hull.back(), a[i])){
  61.             hull.pop_back();
  62.         }
  63.         hull.push_back(a[i]);
  64.     }
  65.     for (int i = a.size() - 2; i >= 0; --i){
  66.         while (hull.size() > 1 && ccw(hull[hull.size() - 2], hull.back(), a[i])){
  67.             hull.pop_back();
  68.         }
  69.         hull.push_back(a[i]);
  70.     }
  71.     if (a.size() > 1){
  72.         hull.pop_back();
  73.     }
  74.     return hull;
  75. }
  76.  
  77. bool onSegment (Point &A, Point &B, Point &C){
  78.     return (cross(A, B, C) == 0 && dot(C, A, B) <= 0);
  79. }
  80.  
  81. bool inHull (vector<Point> &hull, Point P){
  82.     int n = hull.size();
  83.     if (onSegment(hull[0], hull[n - 1], P) || onSegment(hull[0], hull[1], P)){
  84.         return true;
  85.     }
  86.     if (!ccw(hull[0], hull[n - 1], P) && !ccw(hull[1], hull[0], P)){
  87.         return false;
  88.     }
  89.     int l = 1, r = n - 1, id = -1;
  90.     while (l <= r){
  91.         int m = l + r >> 1;
  92.         if (!ccw(hull[0], P, hull[m])){
  93.             id = m;
  94.             r = m - 1;
  95.         } else {
  96.             l = m + 1;
  97.         }
  98.     }
  99.     return (onSegment(hull[id - 1], hull[id], P) || ccw(P, hull[id], hull[id - 1]));
  100. }
  101.  
  102. tuple<db, db, db> getDio (Line A){
  103.     int a = A.y.y - A.x.y;
  104.     int b = A.x.x - A.y.x;
  105.     int c = a * A.x.x + b * A.x.y;
  106.     return make_tuple(a, b, c);
  107. }
  108.  
  109. Point Intersect (Line A, Line B){
  110.     auto [a1, b1, c1] = getDio(A);
  111.     auto [a2, b2, c2] = getDio(B);
  112.     db X = (b2 * c1 - b1 * c2) / (a1 * b2 - b1 * a2);
  113.     db Y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
  114.     Point Z = Point(X, Y);
  115.     if (!onSegment(A.x, A.y, Z) || !onSegment(B.x, B.y, Z)){
  116.         return Point(-1, -1);
  117.     } else {
  118. //        cout << A.x.x << " " << A.x.y << " " << A.y.x << " " << A.y.y << "\n";
  119. //        cout << B.x.x << " " << B.x.y << " " << B.y.x << " " << B.y.y << "\n";
  120. //        cout << Z.x << " " << Z.y << endl;
  121.         return Z;
  122.     }
  123. }
  124.  
  125. void solve (){
  126.     int n, m; cin >> n >> m;
  127.     db ans = 0;
  128.     vector<Point> a(n), b(m);
  129.     for (int i = 0; i < n; ++i){
  130.         cin >> a[i].x >> a[i].y;
  131.     }
  132.     for (int i = 0; i < m; ++i){
  133.         cin >> b[i].x >> b[i].y;
  134.     }
  135.     a = ConvexHull(a);
  136.     b = ConvexHull(b);
  137.     vector<Point> c;
  138.     for (auto &X : a){
  139.         if (inHull(b, X)){
  140.             c.push_back(X);
  141.         }
  142.     }
  143.     for (auto &X : b){
  144.         if (inHull(a, X)){
  145.             c.push_back(X);
  146.         }
  147.     }
  148.     for (int i = 0; i < n; ++i){
  149.         int j = (i + 1) % n;
  150.         for (int k = 0; k < m; ++k){
  151.             int l = (k + 1) % m;
  152.             Point cut = Intersect(Line(a[i], a[j]), Line(b[k], b[l]));
  153.             if (cut != Point(-1, -1)){
  154.                 c.push_back(cut);
  155.             }
  156.         }
  157.     }
  158.     if (c.size() == 0){
  159.         out(0);
  160.         return;
  161.     }
  162.     c = ConvexHull(c);
  163.     for (int i = 0; i < c.size(); ++i){
  164.         int j = (i + 1) % c.size();
  165.         ans += (db)((c[i].x + c[j].x) * (c[i].y - c[j].y) / (db)(2));
  166.     }
  167.     out(ans);
  168. }
  169.  
  170. int32_t main (){
  171.     ios::sync_with_stdio(false); cin.tie(nullptr);
  172.     if (fopen("ipolygon.inp", "r")){
  173.         freopen("ipolygon.inp", "r", stdin);
  174.         freopen("ipolygon.out", "w", stdout);
  175.     }
  176.     int tt; cin >> tt;
  177.     while (tt--){
  178.         solve();
  179.     }
  180. }
  181.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/8wXu6a
language:
C++14 (clang 8.0)
created:
6 hours ago
visibility:
secret

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!