Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <cstring>
- #include <deque>
- #include <stack>
- #include <stdio.h>
- #include <map>
- #include <set>
- #include <time.h>
- #include <string>
- #include <fstream>
- #include <queue>
- #include <bitset>
- #include <cstdlib>
- #define X first
- #define Y second
- #define mp make_pair
- #define pb push_back
- #define pdd pair<double,double>
- #define pii pair<ll,ll>
- #define PI 3.14159265358979323846
- #define MOD 1000000007
- #define MOD2 1000000009
- #define INF ((ll)1e+18)
- #define x1 fldgjdflgjhrthrl
- #define x2 fldgjdflgrtyrtyjl
- #define y1 fldggfhfghjdflgjl
- #define y2 ffgfldgjdflgjl
- #define N 500500
- #define SUM 23423
- #define MAG 1048576
- #define OPEN 0
- #define CLOSE 1
- typedef int ll;
- typedef long double ld;
- using namespace std;
- 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];
- char s[10];
- const double EPS = 1E-9;
- double x,y;
- struct pt {
- double x, y;
- pt()
- {
- }
- pt(double x, double y)
- {
- this->x = x;
- this->y = y;
- }
- bool operator< (const pt & p) const {
- return x < p.x-EPS || abs(x-p.x) < EPS && y < p.y - EPS;
- }
- };
- struct triangle {
- double x[3], y[3];
- };
- double Abs(double x)
- {
- return x>0?x:-x;
- }
- double Stri(double x1, double y1, double x2, double y2, double x3, double y3)
- {
- return ((x1+x2)*(y1-y2)+(x2+x3)*(y2-y3)+(x3+x1)*(y3-y1))/2;
- }
- bool inside_triangle(pt x, triangle y)
- {
- double S = 0;
- for (int i = 0; i < 3; i++)
- {
- double d = Abs(Stri(x.x,x.y,y.x[i],y.y[i],y.x[(i+1)%3],y.y[(i+1)%3]));
- S += d;
- }
- double T = Abs(Stri(y.x[0],y.y[0],y.x[1],y.y[1],y.x[2],y.y[2]));
- //cout << S << " " << T << endl;
- if (abs(S - T)<EPS)
- return true;
- return false;
- }
- struct line {
- double a, b, c;
- line() {}
- line (pt p, pt q) {
- a = p.y - q.y;
- b = q.x - p.x;
- c = - a * p.x - b * p.y;
- norm();
- }
- void norm() {
- double z = sqrt (a*a + b*b);
- if (abs(z) > EPS)
- a /= z, b /= z, c /= z;
- }
- double dist (pt p) const {
- return a * p.x + b * p.y + c;
- }
- };
- #define det(a,b,c,d) (a*d-b*c)
- inline bool betw (double l, double r, double x) {
- return min(l,r) <= x + EPS && x <= max(l,r) + EPS;
- }
- inline bool intersect_1d (double a, double b, double c, double d) {
- if (a > b) swap (a, b);
- if (c > d) swap (c, d);
- return max (a, c) <= min (b, d) + EPS;
- }
- bool intersect (pt a, pt b, pt c, pt d, pt & left, pt & right) {
- if (! intersect_1d (a.x, b.x, c.x, d.x) || ! intersect_1d (a.y, b.y, c.y, d.y))
- return false;
- line m (a, b);
- line n (c, d);
- double zn = det (m.a, m.b, n.a, n.b);
- if (abs (zn) < EPS) {
- if (abs (m.dist (c)) > EPS || abs (n.dist (a)) > EPS)
- return false;
- if (b < a) swap (a, b);
- if (d < c) swap (c, d);
- left = max (a, c);
- right = min (b, d);
- return true;
- }
- else {
- left.x = right.x = - det (m.c, m.b, n.c, n.b) / zn;
- left.y = right.y = - det (m.a, m.c, n.a, n.c) / zn;
- return betw (a.x, b.x, left.x)
- && betw (a.y, b.y, left.y)
- && betw (c.x, d.x, left.x)
- && betw (c.y, d.y, left.y);
- }
- }
- triangle a[105];
- vector<pair<double,double> > f;
- int main() {
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- cin >> n;
- double ans = 0;
- double minx = 1e+9, maxx = -1e+9, miny = 1e+9, maxy = -1e+9;
- for (i = 0; i < n; i++)
- {
- 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];
- for (j = 0; j < 3; j++)
- {
- minx = min(minx, a[i].x[j]);
- maxx = max(maxx, a[i].x[j]);
- miny = min(miny, a[i].y[j]);
- maxy = max(maxy, a[i].y[j]);
- }
- }
- double dy = 10000000./n;
- double dx = (maxx-minx)/dy;
- double kk = 0;
- //cout << minx << " " << maxx << " " << miny << " " << maxy << endl;
- for (double i = minx+dx/2; i <= maxx; i+= dx)
- {
- kk++;
- double y1 = -2000000;
- double y2 = 2000000;
- pt x1(i,y1);
- pt x2(i,y2);
- f.clear();
- for (j = 0; j < n; j++)
- {
- vector<double> g;
- for (k = 0; k < 3; k++)
- {
- pt x3(a[j].x[k], a[j].y[k]);
- pt x4(a[j].x[(k+1)%3], a[j].y[(k+1)%3]);
- pt x5,x6;
- bool flag = intersect(x1,x2,x3,x4,x5,x6);
- if (flag && x5.x == x6.x && x5.y == x6.y)
- g.push_back(x5.y);
- }
- sort(g.begin(), g.end());
- ll sz = g.size();
- if (sz != 0 && g[0] != g[sz-1])
- f.push_back(mp(g[0], g[sz-1]));
- }
- if (f.size() == 0)
- continue;
- sort(f.begin(),f.end());
- double p = 0;
- double l = f[0].X, r = f[0].Y;
- for (j = 1; j < f.size(); j++)
- {
- if (f[j].X >= l && f[j].X <= r)
- r = max(r, f[j].Y);
- else
- {
- p += r-l;
- l = f[j].X;
- r = f[j].Y;
- }
- }
- p += r-l;
- ans += p;
- }
- //cout << kk << endl;
- //cout << num << " " << k << endl;
- printf("%.9f\n",(maxx-minx)*ans/(kk));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement