Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define pb push_back
- #define ff first
- #define ss second
- #define fori(n) for (int i = 0; i < n; i++)
- #define forj(n) for (int j = 0; j < n; j++)
- struct point {
- double x, y;
- };
- struct line {
- double A, B, C;
- };
- double dist(point a, point b) {
- return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- double dist_line(point p, line l) {
- return abs(l.A * p.x + l.B * p.y + l.C) / (sqrt(l.A * l.A + l.B * l.B));
- }
- point make_point(double x, double y) {
- point a;
- a.x = x;
- a.y = y;
- return a;
- }
- line make_line_byPoint(point a, point b) {
- line ans;
- ans.A = a.y - b.y;
- ans.B = b.x - a.x;
- ans.C = a.x * b.y - b.x * a.y;
- return ans;
- }
- line make_line(double A, double B, double C) {
- line a;
- a.A = A;
- a.B = B;
- a.C = C;
- return a;
- }
- point intersect(point a, point b, line lin) {
- point kek = b;
- kek.x -= a.x;
- kek.y -= a.y;
- double l = 0.0, r = 1.0;
- double m1, m2;
- double d1, d2;
- fori(1000) {
- m1 = l + (r - l) / 3;
- m2 = r - (r - l) / 3;
- d1 = dist_line(make_point(a.x + kek.x * m1, a.y + kek.y * m1), lin);
- d2 = dist_line(make_point(a.x + kek.x * m2, a.y + kek.y * m2), lin);
- if (d1 > d2) l = m1;
- else r = m2;
- }
- return make_point(a.x + kek.x * l, a.y + kek.y * l);
- }
- double sq(vector < point > a) {
- double res = 0;
- int j;
- fori(a.size()) {
- if (i == a.size() - 1) j = 0;
- else j = i + 1;
- res += (a[i].x - a[j].x) * (a[i].y + a[j].y);
- }
- return abs(res) / 2.0;
- }
- double eps;
- vector < line > lines;
- double ans = 0;
- void kek(int ind, vector < point > cur) {
- if (ind == lines.size()) {
- ans = max(ans, sq(cur));
- return ;
- }
- vector < pair < int, point > > bubs;
- point b;
- for (int i = 0; i < cur.size(); i++) {
- b = intersect(cur[i], cur[(i + 1) % cur.size()], lines[ind]);
- if (dist_line(b, lines[ind]) > eps) continue;
- if (bubs.size() == 0) {
- bubs.pb({i, b});
- continue;
- }
- if (dist(bubs.back().ss, b) > eps) {
- bubs.pb({i, b});
- }
- }
- if (bubs.size() == 0) {
- kek(ind + 1, cur);
- return ;
- }
- if (bubs.size() == 1) {
- //cout << "on line you f** idiot";
- kek(ind + 1, cur);
- exit(0);
- }
- if (bubs.size() != 2) {
- cout << "something wrong....";
- while (true) ;
- /// если сюда зайдет, то получим tl из-за бесконечного цикла
- exit(0);
- }
- int i1 = bubs[0].ff;
- int i2 = bubs[1].ff;
- vector < point > a1;
- a1.pb(bubs[0].ss);
- for (int i = i1 + 1; i <= i2; i++) a1.pb(cur[i]);
- a1.pb(bubs[1].ss);
- kek(ind + 1, a1);
- a1 = {};
- a1.pb(bubs[1].ss);
- for (int i = i2 + 1; i < cur.size(); i++) a1.pb(cur[i]);
- for (int i = 0; i <= i1; i++) a1.pb(cur[i]);
- a1.pb(bubs[0].ss);
- kek(ind + 1, a1);
- }
- int main() {
- cout << fixed << setprecision(40);
- eps = 0.0000000001;
- vector < pair < pair < int, int >, pair < int, int > > > inp;
- inp = {
- {{50, 32}, {-13, 43}},
- {{23, -34}, {80, 55}}
- };
- fori(inp.size()) {
- point p1 = make_point(inp[i].ff.ff, inp[i].ff.ss);
- point p2 = make_point(inp[i].ss.ff, inp[i].ss.ss);
- lines.pb(make_line_byPoint(p1, p2));
- }
- vector < point > beg;
- beg.pb(make_point(-50, -50));
- beg.pb(make_point(-50, 50));
- beg.pb(make_point(50, 50));
- beg.pb(make_point(50, -50));
- kek(0, beg);
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement