QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#262741#876. Big BrotherFyindCompile Error//Python34.3kb2023-11-23 22:43:162023-11-23 22:43:17

Judging History

你现在查看的是最新测评结果

  • [2023-11-23 22:43:17]
  • 评测
  • [2023-11-23 22:43:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = 1e4 + 5;
int n, m;
#define _ << " "<<
#define sz(x) ((int)x.size())
typedef long double ld;
const ld eps = 1e-17;
struct Point {
    ld x,y;
    Point(ld x=0,ld y = 0) : x(x), y(y) {}
};
ld dcmp(ld x) {
    if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}
typedef Point Vector;
Vector operator+(Vector a, Vector b) { return Vector(a.x+b.x, a.y+b.y); }
Vector operator-(Vector a, Vector b) { return Vector(a.x-b.x, a.y-b.y);}
Vector operator*(Vector a, ld x) { return Vector(a.x*x, a.y*x); }

ld Dot(Vector a,Vector b) { return a.x*b.x + a.y*b.y; }
ld Cross(Vector a, Vector b) { return a.x*b.y-a.y*b.x; }

Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {
    return p + v*(Cross(w,p-q)/Cross(v,w));
}
bool OnSegment(Point p,Point a1,Point a2) {
    return dcmp(Cross(a1-p,a2-p)) == 0 && dcmp(Dot(a1-p,a2-p)) < 0;
}
bool SegmentProperIntersection(Point a1, Point a2,Point b1,Point b2) {
    if (OnSegment(a1, b1,b2) || OnSegment(a2, b1,b2)) return true;
    double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1),c3 = Cross(b2-b1,a1-b1),
    c4 = Cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}
bool up(Point a) {
    return dcmp(a.y) > 0 || (dcmp(a.y) == 0 && dcmp(a.x) >= 0); 
}

ld PolygonArea(deque<Point> &P) {
    ld area = 0;
    for (int i = 1;i < sz(P); ++i) {
        area += Cross(P[i]-P[0], P[(i+1)%sz(P)] - P[0]);
    }
    return abs(area/2);
}

ld Length(Vector v) { return sqrt(Dot(v,v)); }

ld DistanceToLine(Point p, Point a, Point b) {
    Vector v1 = b-a, v2 = p-a;
    return fabs(Cross(v1,v2)) / Length(v1);
}

bool linecmp(pair<Point,Vector> a, pair<Point,Vector> b ) {
    if (Cross(a.second,b.second) == 0 && 
    dcmp(DistanceToLine(a.first,b.first,b.first+b.second)) == 0) return 1;
    return 0;
}

ld solve(vector<pair<Point,Vector>> A) {
    sort(A.begin(), A.end(), [&](auto x,auto y) {
        auto a = x.second; auto b = y.second;
        if (up(a) != up(b)) return up(a) > up(b);
        if (Cross(a,b) == 0) {
            Vector c = x.first - y.first;
            if (Cross(b, c) > 0) return false;
            else return true;
        }
        return Cross(a,b) > 0;
    });
    // cout << "DEG" _ Cross(A[1].second,A[2].second) << endl;
    // Vector c = A[1].first - A[2].first;
    // cout << Cross(A[2].second,c) << endl;
    // for (auto [a,b] : A) {
    //     cout << a.x _ a.y _ b.x _ b.y _ up(b) << endl;
    // }

    deque<Point> P = {A[0].first, A[0].first +A[0].second};
    for (int i = 1;i < sz(A); ++i) {
        if (linecmp(A[i],A[i-1])) continue;
        auto [x,v] = A[i];
        auto y = x + v;
        Point a = P[sz(P)-2], b = P[sz(P)-1]; 
        while (!SegmentProperIntersection(a,b, x,y)) {
            P.pop_back();
            a = P[sz(P)-2], b = P.back();
            break;
        }
        P.pop_back();
        Point nx = GetLineIntersection(a,b-a,x,v);
        P.push_back(nx); P.push_back(y);
    }
    // for (auto a : P) {
    //     cout << a.x _ a.y << endl;
    // }
    auto a = P[0], b = P[1];
    auto x = P[sz(P)-2], y = P[sz(P)-1];
    while (!SegmentProperIntersection(a,b,x,y)) {
        P.pop_front();
        if (sz(P) < 2) {
            cout << 0 << endl;
            exit(0);
        }
        a = P[0], b = P[1];

    }
    P.pop_front();
    Point nx = GetLineIntersection(a,b-a,x,y-x);
    P.push_front(nx); P.pop_back();

    // for (auto a : P) {
    //     cout << a.x _ a.y << endl;
    // }

    return PolygonArea(P);
}
vector<Point> P;

int main() {
    #ifdef LLOCAL
    freopen("a.in", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // cout << Cross(Point(0,1e18),Point(0,-(1e18))) << endl;
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        int x,y; cin >> x >> y;
        P.push_back(Point(x,y));
    }
    vector<pair<Point,Vector>> line;
    for (int i = 0;i < n; ++i) {
        int l = (i-1+n)%n;
        Vector v = Vector(P[l]-P[i]);
        // cout << v.x _ v.y << endl;
        Point np = P[i] + v*(-(1e8));
        // cout << np.x _ np.y << endl;
        line.push_back({np, v*(1e10)});
    }
    ld ans = solve(line);
    cout << fixed << setprecision(6) << ans << endl;
    return 0;
}

Details

  File "answer.code", line 2
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax