fork(2) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <set>
  8. #include <map>
  9. #include <vector>
  10. #include <iomanip>
  11.  
  12. #define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
  13. #define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
  14.  
  15. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  16. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  17. using namespace std;
  18.  
  19. const long double EPS = 1e-6;
  20.  
  21. struct Point {
  22.     long double x, y;
  23.     Point(long double x = 0, long double y = 0) : x(x), y(y) {}
  24.  
  25.     Point operator - (Point a) { return Point(x-a.x, y-a.y); }
  26.  
  27.     long double sqlen() { return x*x + y*y; }
  28.     long double len() { return sqrt(sqlen()); }
  29.  
  30.     void print() { cout << x << ' ' << y << endl; }
  31. } points[111], O(0, 0);
  32.  
  33. int ccw(Point a, Point b, Point c) {
  34.     b = b - a; c = c - a;
  35.     long double t = b.x*c.y - b.y*c.x;
  36.     if (fabs(t) < EPS) return 0;
  37.     else if (t < 0) return -1;
  38.     else return 1;
  39. }
  40.  
  41. bool operator < (const Point &a, const Point &b) {
  42.     int t = ccw(O, a, b);
  43.     if (t == 0) return (const_cast<Point &>(a)).sqlen() < (const_cast<Point &>(b)).sqlen();
  44.     return t > 0;
  45. }
  46.  
  47. long double area(Point a, Point b, Point c) {
  48.     b = b - a; c = c - a;
  49.     long double t = b.x*c.y - b.y*c.x;
  50.     return fabs(t) / 2.0;
  51. }
  52.  
  53. struct Rect {
  54.     Point A, B, C, D;
  55. } a[111];
  56. int n;
  57.  
  58. long double X, Y;
  59. int nPoint;
  60.  
  61. struct Line { long double a, b, c; };          // a way to represent a line
  62.  
  63. void pointsToLine(Point p1, Point p2, Line &l) {
  64.     if (fabs(p1.x - p2.x) < EPS) {              // vertical line is fine
  65.         l.a = 1.0;   l.b = 0.0;   l.c = -p1.x;           // default values
  66.     } else {
  67.         l.a = -(long double)(p1.y - p2.y) / (p1.x - p2.x);
  68.         l.b = 1.0;              // IMPORTANT: we fix the value of b to 1.0
  69.         l.c = -(long double)(l.a * p1.x) - p1.y;
  70.     } 
  71. }
  72.  
  73. bool areParallel(Line l1, Line l2) {       // check coefficients a & b
  74.     return (fabs(l1.a-l2.a) < EPS) && (fabs(l1.b-l2.b) < EPS);
  75. }
  76.  
  77. bool areIntersect(Line l1, Line l2, Point &p) {
  78.     if (areParallel(l1, l2)) return false;            // no intersection
  79.     // solve system of 2 linear algebraic equations with 2 unknowns
  80.     p.x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
  81.     // special case: test for vertical line to avoid division by zero
  82.     if (fabs(l1.b) > EPS) p.y = -(l1.a * p.x + l1.c);
  83.     else                  p.y = -(l2.a * p.x + l2.c);
  84.     return true;
  85. }
  86.  
  87. bool between(Point A, Point B, Point P) {
  88.     return min(A.x, B.x) - EPS <= P.x && P.x <= max(A.x, B.x) + EPS
  89.             && min(A.y, B.y) - EPS <= P.y && P.y <= max(A.y, B.y) + EPS;
  90. }
  91.  
  92. void go(Point A, Point B, Line lA, Line lB, Point &X, Point &Y) {
  93.     if ((A.x > EPS || A.y > EPS) && (B.x > EPS || B.y > EPS)) {
  94.         Line l; pointsToLine(A, B, l);
  95.         Point P, Q;
  96.         if (areIntersect(l, lA, P) && areIntersect(l, lB, Q)) {
  97.             if (between(A, B, P) && between(A, B, Q)) {
  98.                 if (P.len() < X.len()) X = P;
  99.                 if (Q.len() < Y.len()) Y = Q;
  100.             }
  101.         }
  102.     }
  103. }
  104.  
  105. long double calc() {
  106.     nPoint = 0;
  107.     FOR(i,1,n) {
  108.         points[++nPoint] = a[i].A;
  109.         points[++nPoint] = a[i].B;
  110.         points[++nPoint] = a[i].C;
  111.         points[++nPoint] = a[i].D;
  112.     }
  113.     sort(points+1, points+nPoint+1);
  114.     long double res = 0.0;
  115.     FOR(i,1,nPoint-1) {
  116.         Point A = points[i], B = points[i+1];
  117.  
  118.         // cout << "Khe: " << A.x << ' ' << A.y << ' ' << B.x << ' ' << B.y << endl;
  119.         Line lA, lB;
  120.         pointsToLine(O, A, lA);
  121.         pointsToLine(O, B, lB);
  122.  
  123.         Point X(1e5, 1e5), Y(1e5, 1e5);
  124.  
  125.         FOR(r,1,n) {
  126.             Line l;
  127.             go(a[r].A, a[r].B, lA, lB, X, Y);
  128.             go(a[r].B, a[r].C, lA, lB, X, Y);
  129.             go(a[r].C, a[r].D, lA, lB, X, Y);
  130.             go(a[r].D, a[r].A, lA, lB, X, Y);
  131.         }
  132.  
  133.         res += area(O, X, Y);
  134.         // DEBUG(res);
  135.     }
  136.     // cout << endl;
  137.     return res;
  138. }
  139.  
  140. void xoay(Point &P, int turn) {
  141.     if (turn == 0) {
  142.         P.x = X - P.x;
  143.     } else {
  144.         P.y = Y - P.y;
  145.     }
  146. }
  147.  
  148. void reverse(int turn) {
  149.     FOR(i,1,n) {
  150.         xoay(a[i].A, turn);
  151.         xoay(a[i].B, turn);
  152.         xoay(a[i].C, turn);
  153.         xoay(a[i].D, turn);
  154.     }
  155. }
  156.  
  157. int main(int argc, char const *argv[]) {
  158.     int ntest; cin >> ntest;
  159.     cout << (fixed) << setprecision(6);
  160.     while (ntest--) {
  161.         cin >> X >> Y >> n;
  162.         FOR(i,1,n) {
  163.             long double x1, y1, x2, y2;
  164.             cin >> x1 >> y1 >> x2 >> y2;
  165.  
  166.             if (x1 > x2) swap(x1, x2);
  167.             if (y1 > y2) swap(y1, y2);
  168.  
  169.             a[i].A = Point(x1, y1);
  170.             a[i].B = Point(x1, y2);
  171.             a[i].C = Point(x2, y2);
  172.             a[i].D = Point(x2, y1);
  173.         }
  174.         ++n;
  175.         a[n].A = Point(0, 0);
  176.         a[n].B = Point(0, Y);
  177.         a[n].C = Point(X, Y);
  178.         a[n].D = Point(X, 0);
  179.  
  180.         long double res3 = calc();
  181.  
  182.         reverse(0);
  183.         long double res4 = calc();
  184.  
  185.         reverse(1);
  186.         long double res2 = calc();
  187.  
  188.         reverse(0);
  189.         long double res1 = calc();
  190.  
  191.         cout << res1 << ' ' << res2 << endl << res3 << ' ' << res4 << endl;
  192.     }
  193.     return 0;
  194. }
Success #stdin #stdout 0s 3452KB
comments (?)
stdin
copy 
1
4 4
2
1 1 2 2
1 3 3 4
stdout
copy 
4.666667 6.833333
8.250000 9.666667
https://ideone.com/0SOrWG
language:
C++ (gcc 8.3)
created:
10 years 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!