eolymp
bolt
Try our new interface for solving problems
Məsələlər

Yaşıl ləkə

dərc olunub 26.04.22 15:10:53

Блииин... из Bullcode убрали модуль <bullGO!> в котором было очень много функций...

dərc olunub 28.02.24 20:26:07

include <iostream>

include <vector>

include <cmath>

include <algorithm>

const double EPS = 1e-9;

int sgn(double x) { if (fabs(x) < EPS) return 0; return (x > 0) ? 1 : -1; }

int kramer(double a1, double b1, double c1, double a2, double b2, double c2, double *x, double *y) { double d = a1 * b2 - a2 * b1; double dx = c1 * b2 - c2 * b1; double dy = a1 * c2 - a2 * c1;

if (!d) return (dx == 0.0) + 1;

*x = dx / d;
*y = dy / d;

return 0;

}

int solve(std::pair<double, double> p1, std::pair<double, double> p2, std::pair<double, double> p3, std::pair<double, double> p4, double *xc, double *yc) { double a1 = p2.first - p1.first; double b1 = p3.first - p4.first; double c1 = p3.first - p1.first; double a2 = p2.second - p1.second; double b2 = p3.second - p4.second; double c2 = p3.second - p1.second; double t1, t2;

int status = kramer(a1, b1, c1, a2, b2, c2, &t1, &t2);

if (status || !((t1 >= 0.0) && (t1 <= 1.0)) || !((t2 >= 0.0) && (t2 <= 1.0))) return 1;

*xc = p1.first + (p2.first - p1.first) * t1;
*yc = p1.second + (p2.second - p1.second) * t1;

return 0;

}

void add(double x, double y, std::vector<std::pair<double, double>> &v) { for (int i = 0; i < v.size(); i++) { if ((fabs(v[i].first - x) < EPS) && (fabs(v[i].second - y) < EPS)) return; } v.pushback(std::makepair(x, y)); }

int InTriangle(std::pair<double, double> *m, std::pair<double, double> Point) { int i, res; double ax, ay, bx, by;

for (res = i = 0; i < 3; i++) {
    ax = m[i + 1].first - m[i].first;
    ay = m[i + 1].second - m[i].second;
    bx = Point.first - m[i + 1].first;
    by = Point.second - m[i + 1].second;
    res += sgn(ax * by - ay * bx);
}

return (fabs(fabs(res) - 3.0) < EPS);

}

double len2(std::pair<double, double> p) { return p.first * p.first + p.second * p.second; }

double PolarAngle(std::pair<double, double> p) { return atan2(p.second, p.first); }

int f(std::pair<double, double> a, std::pair<double, double> b) { if (fabs(PolarAngle(a) - PolarAngle(b)) < EPS) return len2(a) < len2(b); return PolarAngle(a) < PolarAngle(b); }

double findArea(const std::vector<std::pair<double, double>> &v) { double area = 0.0; int n = v.size();

for (int i = 0; i < n; i++) {
    int next = (i + 1) % n;
    area += (v[i].first * v[next].second - v[next].first * v[i].second);
}

return fabs(area) / 2.0;

}

int main() { std::pair<double, double> p1[4], p2[4]; std::vector<std::pair<double, double>> v; double xc, yc;

scanf("%lf %lf %lf %lf %lf %lf", &p1[0].first, &p1[0].second, &p1[1].first,
      &p1[1].second, &p1[2].first, &p1[2].second);
p1[3] = p1[0];

scanf("%lf %lf %lf %lf %lf %lf", &p2[0].first, &p2[0].second,
      &p2[1].first, &p2[1].second, &p2[2].first, &p2[2].second);
p2[3] = p2[0];

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        int status = solve(p1[i], p1[i + 1], p2[j], p2[j + 1], &xc, &yc);
        if (!status) add(xc, yc, v);
    }
}

for (int i = 0; i < 3; i++)
    if (InTriangle(p1, p2[i])) add(p2[i].first, p2[i].second, v);
for (int i = 0; i < 3; i++)
    if (InTriangle(p2, p1[i])) add(p1[i].first, p1[i].second, v);

for (int i = 1; i < v.size(); i++) {
    if (v[i].first < v[0].first) std::swap(v[i], v[0]);
    if ((v[i].first == v[0].first) && (v[i].second < v[0].second))
        std::swap(v[i], v[0]);
}

int num = 0;
double s = 0;

if (v.size() == 0) {
    printf("%d %.2lf\n", num, s);
    return 0;
}

if (v.size() == 2) {
    printf("%d %.2lf\n", num, s);
    return 0;
}

std::pair<double, double> Center = v[0];
for (int i = 0; i < v.size(); i++) {
    v[i].first = v[i].first - Center.first;
    v[i].second = v[i].second - Center.second;
}

std::sort(v.begin() + 1, v.end(), f);

for (int i = 0; i < v.size(); i++) {
    v[i].first = v[i].first + Center.first;
    v[i].second = v[i].second + Center.second;
}

s = findArea(v);
num = v.size();

if (fabs(s) < 0.005) num = 1;

printf("%d %.2lf\n", num, s);

return 0;

}