fork download
copy 
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <stack>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. #define EPS 1e-9
  9. #define PI acos(-1.0)
  10.  
  11. double DEG_to_RAD(double d) {
  12. 	return d * PI / 180.0;
  13. }
  14.  
  15. double RAD_to_DEG(double r) {
  16. 	return r * 180.0 / PI;
  17. }
  18.  
  19. struct point {
  20. 	double x, y; // we use double for most examples in this source code
  21. 	point() {
  22. 	}
  23. 	;
  24. 	point(double _x, double _y) {
  25. 		x = _x, y = _y;
  26. 	}
  27. 	bool operator <(point p) const { // declare as const otherwise won't compile
  28. 		if (fabs(x - p.x) > EPS)
  29. 			return x < p.x;
  30. 		return y < p.y;
  31. 	}
  32. 	bool operator ==(point p) const {
  33. 		return fabs(x - p.x) < EPS && fabs(x - p.y) < EPS;
  34. 	}
  35. };
  36.  
  37. struct vec {
  38. 	double x, y; // similar to point
  39. 	vec(double _x, double _y) {
  40. 		x = _x, y = _y;
  41. 	}
  42. };
  43.  
  44. vec toVector(point p1, point p2) { // convert 2 points to vector
  45. 	return vec(p2.x - p1.x, p2.y - p1.y);
  46. }
  47.  
  48. double dist(point p1, point p2) { // get Euclidean distance of two points
  49. 	return hypot(p1.x - p2.x, p1.y - p2.y);
  50. } // as shown earlier
  51.  
  52. // returns the area, which is half the determinant
  53. // works for both convex and concave polygons
  54. double area(const vector<point> &P) {
  55. 	double result = 0.0, x1, y1, x2, y2;
  56. 	for (int i = 0; i < (int) P.size() - 1; i++) {
  57. 		x1 = P[i].x;
  58. 		x2 = P[i + 1].x;
  59. 		y1 = P[i].y;
  60. 		y2 = P[i + 1].y;
  61. 		result += (x1 * y2 - x2 * y1);
  62. 	}
  63. 	return fabs(result) / 2.0;
  64. }
  65.  
  66. double dot(vec a, vec b) {
  67. 	return (a.x * b.x + a.y * b.y);
  68. }
  69.  
  70. double norm_sq(vec v) {
  71. 	return v.x * v.x + v.y * v.y;
  72. }
  73.  
  74. double angle(point a, point o, point b) { // returns angle aob in rad
  75. 	vec oa = toVector(o, a), ob = toVector(o, b);
  76. 	return acos(dot(oa, ob) / sqrt(norm_sq(oa) * norm_sq(ob)));
  77. }
  78.  
  79. double cross(vec a, vec b) {
  80. 	return a.x * b.y - a.y * b.x;
  81. }
  82.  
  83. // note: to accept collinear points, we have to change the `> 0'
  84. // returns true if point r is on the left side of line pq
  85. bool ccw(point p, point q, point r) {
  86. 	return cross(toVector(p, q), toVector(p, r)) > 0;
  87. }
  88.  
  89. // returns true if point r is on the same line as the line pq
  90. bool collinear(point p, point q, point r) {
  91. 	return fabs(cross(toVector(p, q), toVector(p, r))) < EPS;
  92. }
  93.  
  94. // returns true if point p is in either convex/concave polygon P
  95. bool inPolygon(point p, const vector<point> &P) {
  96. 	if ((int) P.size() == 0)
  97. 		return false;
  98. 	double sum = 0; // assume first vertex = last vertex
  99. 	for (int i = 0; i < (int) P.size() - 1; i++) {
  100. 		if (ccw(p, P[i], P[i + 1]))
  101. 			sum += angle(P[i], p, P[i + 1]);   // left turn/ccw
  102. 		else
  103. 			sum -= angle(P[i], p, P[i + 1]);
  104. 	} // right turn/cw
  105. 	return fabs(fabs(sum) - 2 * PI) < EPS;
  106. }
  107.  
  108. // line segment p-q intersect with line A-B.
  109. point lineIntersectSeg(point p, point q, point A, point B) {
  110. 	double a = B.y - A.y;
  111. 	double b = A.x - B.x;
  112. 	double c = B.x * A.y - A.x * B.y;
  113. 	double u = fabs(a * p.x + b * p.y + c);
  114. 	double v = fabs(a * q.x + b * q.y + c);
  115. 	return point((p.x * v + q.x * u) / (u + v), (p.y * v + q.y * u) / (u + v));
  116. }
  117.  
  118. // cuts polygon Q along the line formed by point a -> point b
  119. // (note: the last point must be the same as the first point)
  120. vector<point> cutPolygon(point a, point b, const vector<point> &Q) {
  121. 	vector<point> P;
  122. 	for (int i = 0; i < (int) Q.size(); i++) {
  123. 		double left1 = cross(toVector(a, b), toVector(a, Q[i])), left2 = 0;
  124. 		if (i != (int) Q.size() - 1)
  125. 			left2 = cross(toVector(a, b), toVector(a, Q[i + 1]));
  126. 		if (left1 > -EPS)
  127. 			P.push_back(Q[i]); // Q[i] is on the left of ab
  128. 		if (left1 * left2 < -EPS) // edge (Q[i], Q[i+1]) crosses line ab
  129. 			P.push_back(lineIntersectSeg(Q[i], Q[i + 1], a, b));
  130. 	}
  131. 	if (!P.empty()
  132. 			&& (fabs(P.back().x - P.front().x) > EPS
  133. 					|| fabs(P.back().y - P.front().y) > EPS))
  134. 		P.push_back(P.front()); // make P's first point = P's last point
  135. 	return P;
  136. }
  137.  
  138. int main() {
  139. 	int N, W, H, x, y, count = 1;
  140. 	vector<point> P;
  141.  
  142. 	while (scanf("%d %d %d %d %d", &N, &W, &H, &x, &y) != EOF) {
  143. 		P.clear();
  144. 		P.push_back(point(0, 0));
  145. 		P.push_back(point(W, 0));
  146. 		P.push_back(point(W, H));
  147. 		P.push_back(point(0, H));
  148. 		P.push_back(point(0, 0));
  149. 		point fountain(x, y);
  150.  
  151. 		point p1, p2;
  152. 		for (int i = 0; i < N; i++) {
  153. 			scanf("%lf %lf %lf %lf", &p1.x, &p1.y, &p2.x, &p2.y);
  154. 			if (ccw(p1, p2, fountain))
  155. 				P = cutPolygon(p1, p2, P);
  156. 			else
  157. 				P = cutPolygon(p2, p1, P);
  158. 		}
  159.  
  160. 		printf("Case #%d: %.3lf\n", count++, area(P));
  161. 	}
  162. 	return 0;
  163. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
3 100 100 20 30
0 0 100 100
100 0 0 100
0 40 40 100
6 100 100 35 35
0 5 100 5
0 15 100 15
0 30 100 30
0 50 100 50
0 75 100 75
0 98 100 98
0 19250 19250 25 25
5 100000 2000 50000 1001
0 0 50000 2000
50000 2000 100000 0
0 2000 50000 0
50000 0 100000 2000
0 1000 100000 1000
9 100 100 50 99
0 50 50 100
50 100 100 50
100 50 50 0
50 0 0 50
0 0 100 100
0 100 100 0
0 50 100 50
75 100 100 50
75 100 0 50
4 10 10 3 5
0 5 6 10
0 9 7 0
3 10 10 0
5 0 5 10
4 3 3 1 1
0 3 2 0
0 2 1 3
1 3 3 0
0 1 2 3
 498 1000 1000 82 82
0 4 1000 4
4 0 4 1000
0 8 1000 8
8 0 8 1000
0 12 1000 12
12 0 12 1000
0 16 1000 16
16 0 16 1000
0 20 1000 20
20 0 20 1000
0 24 1000 24
24 0 24 1000
0 28 1000 28
28 0 28 1000
0 32 1000 32
32 0 32 1000
0 36 1000 36
36 0 36 1000
0 40 1000 40
40 0 40 1000
0 44 1000 44
44 0 44 1000
0 48 1000 48
48 0 48 1000
0 52 1000 52
52 0 52 1000
0 56 1000 56
56 0 56 1000
0 60 1000 60
60 0 60 1000
0 64 1000 64
64 0 64 1000
0 68 1000 68
68 0 68 1000
0 72 1000 72
72 0 72 1000
0 76 1000 76
76 0 76 1000
0 80 1000 80
80 0 80 1000
0 84 1000 84
84 0 84 1000
0 88 1000 88
88 0 88 1000
0 92 1000 92
92 0 92 1000
0 96 1000 96
96 0 96 1000
0 100 1000 100
100 0 100 1000
0 104 1000 104
104 0 104 1000
0 108 1000 108
108 0 108 1000
0 112 1000 112
112 0 112 1000
0 116 1000 116
116 0 116 1000
0 120 1000 120
120 0 120 1000
0 124 1000 124
124 0 124 1000
0 128 1000 128
128 0 128 1000
0 132 1000 132
132 0 132 1000
0 136 1000 136
136 0 136 1000
0 140 1000 140
140 0 140 1000
0 144 1000 144
144 0 144 1000
0 148 1000 148
148 0 148 1000
0 152 1000 152
152 0 152 1000
0 156 1000 156
156 0 156 1000
0 160 1000 160
160 0 160 1000
0 164 1000 164
164 0 164 1000
0 168 1000 168
168 0 168 1000
0 172 1000 172
172 0 172 1000
0 176 1000 176
176 0 176 1000
0 180 1000 180
180 0 180 1000
0 184 1000 184
184 0 184 1000
0 188 1000 188
188 0 188 1000
0 192 1000 192
192 0 192 1000
0 196 1000 196
196 0 196 1000
0 200 1000 200
200 0 200 1000
0 204 1000 204
204 0 204 1000
0 208 1000 208
208 0 208 1000
0 212 1000 212
212 0 212 1000
0 216 1000 216
216 0 216 1000
0 220 1000 220
220 0 220 1000
0 224 1000 224
224 0 224 1000
0 228 1000 228
228 0 228 1000
0 232 1000 232
232 0 232 1000
0 236 1000 236
236 0 236 1000
0 240 1000 240
240 0 240 1000
0 244 1000 244
244 0 244 1000
0 248 1000 248
248 0 248 1000
0 252 1000 252
252 0 252 1000
0 256 1000 256
256 0 256 1000
0 260 1000 260
260 0 260 1000
0 264 1000 264
264 0 264 1000
0 268 1000 268
268 0 268 1000
0 272 1000 272
272 0 272 1000
0 276 1000 276
276 0 276 1000
0 280 1000 280
280 0 280 1000
0 284 1000 284
284 0 284 1000
0 288 1000 288
288 0 288 1000
0 292 1000 292
292 0 292 1000
0 296 1000 296
296 0 296 1000
0 300 1000 300
300 0 300 1000
0 304 1000 304
304 0 304 1000
0 308 1000 308
308 0 308 1000
0 312 1000 312
312 0 312 1000
0 316 1000 316
316 0 316 1000
0 320 1000 320
320 0 320 1000
0 324 1000 324
324 0 324 1000
0 328 1000 328
328 0 328 1000
0 332 1000 332
332 0 332 1000
0 336 1000 336
336 0 336 1000
0 340 1000 340
340 0 340 1000
0 344 1000 344
344 0 344 1000
0 348 1000 348
348 0 348 1000
0 352 1000 352
352 0 352 1000
0 356 1000 356
356 0 356 1000
0 360 1000 360
360 0 360 1000
0 364 1000 364
364 0 364 1000
0 368 1000 368
368 0 368 1000
0 372 1000 372
372 0 372 1000
0 376 1000 376
376 0 376 1000
0 380 1000 380
380 0 380 1000
0 384 1000 384
384 0 384 1000
0 388 1000 388
388 0 388 1000
0 392 1000 392
392 0 392 1000
0 396 1000 396
396 0 396 1000
0 400 1000 400
400 0 400 1000
0 404 1000 404
404 0 404 1000
0 408 1000 408
408 0 408 1000
0 412 1000 412
412 0 412 1000
0 416 1000 416
416 0 416 1000
0 420 1000 420
420 0 420 1000
0 424 1000 424
424 0 424 1000
0 428 1000 428
428 0 428 1000
0 432 1000 432
432 0 432 1000
0 436 1000 436
436 0 436 1000
0 440 1000 440
440 0 440 1000
0 444 1000 444
444 0 444 1000
0 448 1000 448
448 0 448 1000
0 452 1000 452
452 0 452 1000
0 456 1000 456
456 0 456 1000
0 460 1000 460
460 0 460 1000
0 464 1000 464
464 0 464 1000
0 468 1000 468
468 0 468 1000
0 472 1000 472
472 0 472 1000
0 476 1000 476
476 0 476 1000
0 480 1000 480
480 0 480 1000
0 484 1000 484
484 0 484 1000
0 488 1000 488
488 0 488 1000
0 492 1000 492
492 0 492 1000
0 496 1000 496
496 0 496 1000
0 500 1000 500
500 0 500 1000
0 504 1000 504
504 0 504 1000
0 508 1000 508
508 0 508 1000
0 512 1000 512
512 0 512 1000
0 516 1000 516
516 0 516 1000
0 520 1000 520
520 0 520 1000
0 524 1000 524
524 0 524 1000
0 528 1000 528
528 0 528 1000
0 532 1000 532
532 0 532 1000
0 536 1000 536
536 0 536 1000
0 540 1000 540
540 0 540 1000
0 544 1000 544
544 0 544 1000
0 548 1000 548
548 0 548 1000
0 552 1000 552
552 0 552 1000
0 556 1000 556
556 0 556 1000
0 560 1000 560
560 0 560 1000
0 564 1000 564
564 0 564 1000
0 568 1000 568
568 0 568 1000
0 572 1000 572
572 0 572 1000
0 576 1000 576
576 0 576 1000
0 580 1000 580
580 0 580 1000
0 584 1000 584
584 0 584 1000
0 588 1000 588
588 0 588 1000
0 592 1000 592
592 0 592 1000
0 596 1000 596
596 0 596 1000
0 600 1000 600
600 0 600 1000
0 604 1000 604
604 0 604 1000
0 608 1000 608
608 0 608 1000
0 612 1000 612
612 0 612 1000
0 616 1000 616
616 0 616 1000
0 620 1000 620
620 0 620 1000
0 624 1000 624
624 0 624 1000
0 628 1000 628
628 0 628 1000
0 632 1000 632
632 0 632 1000
0 636 1000 636
636 0 636 1000
0 640 1000 640
640 0 640 1000
0 644 1000 644
644 0 644 1000
0 648 1000 648
648 0 648 1000
0 652 1000 652
652 0 652 1000
0 656 1000 656
656 0 656 1000
0 660 1000 660
660 0 660 1000
0 664 1000 664
664 0 664 1000
0 668 1000 668
668 0 668 1000
0 672 1000 672
672 0 672 1000
0 676 1000 676
676 0 676 1000
0 680 1000 680
680 0 680 1000
0 684 1000 684
684 0 684 1000
0 688 1000 688
688 0 688 1000
0 692 1000 692
692 0 692 1000
0 696 1000 696
696 0 696 1000
0 700 1000 700
700 0 700 1000
0 704 1000 704
704 0 704 1000
0 708 1000 708
708 0 708 1000
0 712 1000 712
712 0 712 1000
0 716 1000 716
716 0 716 1000
0 720 1000 720
720 0 720 1000
0 724 1000 724
724 0 724 1000
0 728 1000 728
728 0 728 1000
0 732 1000 732
732 0 732 1000
0 736 1000 736
736 0 736 1000
0 740 1000 740
740 0 740 1000
0 744 1000 744
744 0 744 1000
0 748 1000 748
748 0 748 1000
0 752 1000 752
752 0 752 1000
0 756 1000 756
756 0 756 1000
0 760 1000 760
760 0 760 1000
0 764 1000 764
764 0 764 1000
0 768 1000 768
768 0 768 1000
0 772 1000 772
772 0 772 1000
0 776 1000 776
776 0 776 1000
0 780 1000 780
780 0 780 1000
0 784 1000 784
784 0 784 1000
0 788 1000 788
788 0 788 1000
0 792 1000 792
792 0 792 1000
0 796 1000 796
796 0 796 1000
0 800 1000 800
800 0 800 1000
0 804 1000 804
804 0 804 1000
0 808 1000 808
808 0 808 1000
0 812 1000 812
812 0 812 1000
0 816 1000 816
816 0 816 1000
0 820 1000 820
820 0 820 1000
0 824 1000 824
824 0 824 1000
0 828 1000 828
828 0 828 1000
0 832 1000 832
832 0 832 1000
0 836 1000 836
836 0 836 1000
0 840 1000 840
840 0 840 1000
0 844 1000 844
844 0 844 1000
0 848 1000 848
848 0 848 1000
0 852 1000 852
852 0 852 1000
0 856 1000 856
856 0 856 1000
0 860 1000 860
860 0 860 1000
0 864 1000 864
864 0 864 1000
0 868 1000 868
868 0 868 1000
0 872 1000 872
872 0 872 1000
0 876 1000 876
876 0 876 1000
0 880 1000 880
880 0 880 1000
0 884 1000 884
884 0 884 1000
0 888 1000 888
888 0 888 1000
0 892 1000 892
892 0 892 1000
0 896 1000 896
896 0 896 1000
0 900 1000 900
900 0 900 1000
0 904 1000 904
904 0 904 1000
0 908 1000 908
908 0 908 1000
0 912 1000 912
912 0 912 1000
0 916 1000 916
916 0 916 1000
0 920 1000 920
920 0 920 1000
0 924 1000 924
924 0 924 1000
0 928 1000 928
928 0 928 1000
0 932 1000 932
932 0 932 1000
0 936 1000 936
936 0 936 1000
0 940 1000 940
940 0 940 1000
0 944 1000 944
944 0 944 1000
0 948 1000 948
948 0 948 1000
0 952 1000 952
952 0 952 1000
0 956 1000 956
956 0 956 1000
0 960 1000 960
960 0 960 1000
0 964 1000 964
964 0 964 1000
0 968 1000 968
968 0 968 1000
0 972 1000 972
972 0 972 1000
0 976 1000 976
976 0 976 1000
0 980 1000 980
980 0 980 1000
0 984 1000 984
984 0 984 1000
0 988 1000 988
988 0 988 1000
0 992 1000 992
992 0 992 1000
0 996 1000 996
996 0 996 1000
stdout
copy 
Case #1: 1780.000
Case #2: 2000.000
Case #3: 370562500.000
Case #4: 25000000.000
Case #5: 375.000
Case #6: 25.153
Case #7: 2.200
Case #8: 16.000
https://ideone.com/gv8CqX
language:
C++ (gcc 8.3)
created:
11 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!