Submission #1308568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308568		vili	SIR (COI15_sir)	C++20	0 / 100	1096 ms	14968 KiB

sir

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<ll,ll>;

// cross product OA x OB
ll cross(const P& O, const P& A, const P& B) {
    return (A.first - O.first) * (B.second - O.second)
         - (A.second - O.second) * (B.first - O.first);
}

// 2D convex hull using Andrew's monotone chain
vector<P> convex_hull(vector<P> pts) {
    sort(pts.begin(), pts.end());
    int n = pts.size();
    if (n <= 1) return pts;

    vector<P> hull;

    // lower hull
    for (auto &p : pts) {
        while (hull.size() >= 2 &&
               cross(hull[hull.size()-2], hull.back(), p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }

    // upper hull
    int lower_size = hull.size();
    for (int i = n-2; i >= 0; i--) {
        while ((int)hull.size() > lower_size &&
               cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }

    hull.pop_back(); // first==last
    return hull;
}

// area of triangle ABC * 2
ll area2(const P& A, const P& B, const P& C) {
    return llabs(cross(A,B,C));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin >> n;
    vector<P> v(n);
    for (int i=0;i<n;i++) cin >> v[i].first >> v[i].second;

    cin >> m;
    vector<P> v2(m);
    for (int i=0;i<m;i++) cin >> v2[i].first >> v2[i].second;

    // convex hull of v2
    vector<P> hull = convex_hull(v2);

    ll max_area = 0;

    // brute-force two points from v and one point from hull
    for (int i=0;i<n;i++) {
        for (int j=i+1;j<n;j++) {
            int k = 0;
            int sz = hull.size();
            // rotating calipers to maximize triangle area
            for (int t=0;t<sz;t++) {
                ll a = area2(v[i], v[j], hull[t]);
                if (a > max_area) max_area = a;
            }
        }
    }

    cout << max_area << "\n"; // area * 2
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49