Advertisement
Guest User

Untitled

a guest
Nov 12th, 2016
554
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstring>
  6. #include <deque>
  7. #include <stack>
  8. #include <stdio.h>
  9. #include <map>
  10. #include <set>
  11. #include <time.h>
  12. #include <string>
  13. #include <fstream>
  14. #include <queue>
  15. #include <bitset>
  16. #include <cstdlib>
  17. #define X first
  18. #define Y second
  19. #define mp make_pair
  20. #define pb push_back
  21. #define pdd pair<double,double>
  22. #define pii pair<ll,ll>
  23. #define PI 3.14159265358979323846
  24. #define MOD 1000000007
  25. #define MOD2 1000000009
  26. #define INF ((ll)1e+18)
  27. #define x1 fldgjdflgjhrthrl
  28. #define x2 fldgjdflgrtyrtyjl
  29. #define y1 fldggfhfghjdflgjl
  30. #define y2 ffgfldgjdflgjl
  31. #define N 500500
  32. #define SUM 23423
  33. #define MAG 1048576
  34. #define OPEN 0
  35. #define CLOSE 1
  36. typedef int ll;
  37. typedef long double ld;
  38. using namespace std;
  39. ll i,j,n,k,l,m,tot, flag,h,r,ans,z, K,x1,y1,x2,y2,x3,y3,mmx,mmy, b[90050][350];
  40. char s[10];
  41. const double EPS = 1E-9;
  42. double x,y;
  43.  
  44. struct pt {
  45. double x, y;
  46. pt()
  47. {
  48. }
  49. pt(double x, double y)
  50. {
  51. this->x = x;
  52. this->y = y;
  53. }
  54.  
  55. bool operator< (const pt & p) const {
  56. return x < p.x-EPS || abs(x-p.x) < EPS && y < p.y - EPS;
  57. }
  58. };
  59. struct triangle {
  60. double x[3], y[3];
  61. };
  62. double Abs(double x)
  63. {
  64. return x>0?x:-x;
  65. }
  66. double Stri(double x1, double y1, double x2, double y2, double x3, double y3)
  67. {
  68. return ((x1+x2)*(y1-y2)+(x2+x3)*(y2-y3)+(x3+x1)*(y3-y1))/2;
  69. }
  70.  
  71. bool inside_triangle(pt x, triangle y)
  72. {
  73. double S = 0;
  74. for (int i = 0; i < 3; i++)
  75. {
  76. double d = Abs(Stri(x.x,x.y,y.x[i],y.y[i],y.x[(i+1)%3],y.y[(i+1)%3]));
  77. S += d;
  78. }
  79. double T = Abs(Stri(y.x[0],y.y[0],y.x[1],y.y[1],y.x[2],y.y[2]));
  80. //cout << S << " " << T << endl;
  81. if (abs(S - T)<EPS)
  82. return true;
  83. return false;
  84. }
  85.  
  86. struct line {
  87. double a, b, c;
  88.  
  89. line() {}
  90. line (pt p, pt q) {
  91. a = p.y - q.y;
  92. b = q.x - p.x;
  93. c = - a * p.x - b * p.y;
  94. norm();
  95. }
  96.  
  97. void norm() {
  98. double z = sqrt (a*a + b*b);
  99. if (abs(z) > EPS)
  100. a /= z, b /= z, c /= z;
  101. }
  102.  
  103. double dist (pt p) const {
  104. return a * p.x + b * p.y + c;
  105. }
  106. };
  107.  
  108. #define det(a,b,c,d) (a*d-b*c)
  109.  
  110. inline bool betw (double l, double r, double x) {
  111. return min(l,r) <= x + EPS && x <= max(l,r) + EPS;
  112. }
  113.  
  114. inline bool intersect_1d (double a, double b, double c, double d) {
  115. if (a > b) swap (a, b);
  116. if (c > d) swap (c, d);
  117. return max (a, c) <= min (b, d) + EPS;
  118. }
  119.  
  120. bool intersect (pt a, pt b, pt c, pt d, pt & left, pt & right) {
  121. if (! intersect_1d (a.x, b.x, c.x, d.x) || ! intersect_1d (a.y, b.y, c.y, d.y))
  122. return false;
  123. line m (a, b);
  124. line n (c, d);
  125. double zn = det (m.a, m.b, n.a, n.b);
  126. if (abs (zn) < EPS) {
  127. if (abs (m.dist (c)) > EPS || abs (n.dist (a)) > EPS)
  128. return false;
  129. if (b < a) swap (a, b);
  130. if (d < c) swap (c, d);
  131. left = max (a, c);
  132. right = min (b, d);
  133. return true;
  134. }
  135. else {
  136. left.x = right.x = - det (m.c, m.b, n.c, n.b) / zn;
  137. left.y = right.y = - det (m.a, m.c, n.a, n.c) / zn;
  138. return betw (a.x, b.x, left.x)
  139. && betw (a.y, b.y, left.y)
  140. && betw (c.x, d.x, left.x)
  141. && betw (c.y, d.y, left.y);
  142. }
  143. }
  144.  
  145. triangle a[105];
  146. vector<pair<double,double> > f;
  147.  
  148. int main() {
  149. //freopen("input.txt","r",stdin);
  150. //freopen("output.txt","w",stdout);
  151. cin >> n;
  152. double ans = 0;
  153. double minx = 1e+9, maxx = -1e+9, miny = 1e+9, maxy = -1e+9;
  154. for (i = 0; i < n; i++)
  155. {
  156. cin >> a[i].x[0] >> a[i].y[0] >> a[i].x[1] >> a[i].y[1] >> a[i].x[2] >> a[i].y[2];
  157. for (j = 0; j < 3; j++)
  158. {
  159. minx = min(minx, a[i].x[j]);
  160. maxx = max(maxx, a[i].x[j]);
  161. miny = min(miny, a[i].y[j]);
  162. maxy = max(maxy, a[i].y[j]);
  163. }
  164. }
  165. double dy = 10000000./n;
  166. double dx = (maxx-minx)/dy;
  167. double kk = 0;
  168. //cout << minx << " " << maxx << " " << miny << " " << maxy << endl;
  169. for (double i = minx+dx/2; i <= maxx; i+= dx)
  170. {
  171. kk++;
  172. double y1 = -2000000;
  173. double y2 = 2000000;
  174. pt x1(i,y1);
  175. pt x2(i,y2);
  176. f.clear();
  177. for (j = 0; j < n; j++)
  178. {
  179. vector<double> g;
  180. for (k = 0; k < 3; k++)
  181. {
  182. pt x3(a[j].x[k], a[j].y[k]);
  183. pt x4(a[j].x[(k+1)%3], a[j].y[(k+1)%3]);
  184. pt x5,x6;
  185. bool flag = intersect(x1,x2,x3,x4,x5,x6);
  186. if (flag && x5.x == x6.x && x5.y == x6.y)
  187. g.push_back(x5.y);
  188. }
  189. sort(g.begin(), g.end());
  190. ll sz = g.size();
  191. if (sz != 0 && g[0] != g[sz-1])
  192. f.push_back(mp(g[0], g[sz-1]));
  193. }
  194. if (f.size() == 0)
  195. continue;
  196. sort(f.begin(),f.end());
  197. double p = 0;
  198. double l = f[0].X, r = f[0].Y;
  199. for (j = 1; j < f.size(); j++)
  200. {
  201. if (f[j].X >= l && f[j].X <= r)
  202. r = max(r, f[j].Y);
  203. else
  204. {
  205. p += r-l;
  206. l = f[j].X;
  207. r = f[j].Y;
  208. }
  209. }
  210. p += r-l;
  211. ans += p;
  212. }
  213. //cout << kk << endl;
  214. //cout << num << " " << k << endl;
  215. printf("%.9f\n",(maxx-minx)*ans/(kk));
  216. return 0;
  217. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement