oj.uz

Submission #40034

# Submission time Handle Problem Language Result Execution time Memory
40034 2018-01-25T14:00:32 Z krauch SIR (COI15_sir) C++14
100 / 100
 579 ms 49876 KB 
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;


#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

#define fname ""

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 1e6 + 6;

int n, m, sz;
bool u[N];
PII a[N], b[N], c[N];

ll cross(PII a, PII b) {
    return 1ll * a.F * b.S - 1ll * a.S * b.F;
}

bool cmp(PII a, PII a2) {
    if (cross(PII(a.F - b[1].F, a.S - b[1].S), PII(a2.F - b[1].F, a2.S - b[1].S)) != 0) return cross(PII(a.F - b[1].F, a.S - b[1].S), PII(a2.F - b[1].F, a2.S - b[1].S)) > 0;
    return 1ll * (a.F - b[1].F) * (a.F - b[1].F) + 1ll * (a.S - b[1].S) * (a.S - b[1].S) < 1ll * (a2.F - b[1].F) * (a2.F - b[1].F) + 1ll * (a2.S - b[1].S) * (a2.S - b[1].S);
}

main() {
	#ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    cin >> n;
    forn(i, 1, n) {
        cin >> a[i].F >> a[i].S;
        a[i + n] = a[i];
    }

    cin >> m;
    int mn = 1;
    ll kek = ool;
    forn(i, 1, m) {
        cin >> b[i].F >> b[i].S;
        if (b[i].S < b[mn].S || (b[i].S == b[mn].S && b[i].F > b[mn].F)) mn = i;
        kek = min(kek, b[i].F);
    }

    swap(b[1], b[mn]);
    sort(b + 2, b + m + 1, cmp);

    c[++sz] = b[1];
    if (m > 1) c[++sz] = b[2];
    forn(i, 3, m) {
        while (sz > 1 && cross(PII(b[i].F - c[sz - 1].F, b[i].S - c[sz - 1].S), PII(c[sz].F - c[sz - 1].F, c[sz].S - c[sz - 1].S)) >= 0) {
            --sz;
        }
        c[++sz] = b[i];
    }
    while (sz > 2 && cross(PII(b[1].F - c[sz - 1].F, b[1].S - c[sz - 1].S), PII(c[sz].F - c[sz - 1].F, c[sz].S - c[sz - 1].S)) >= 0) {
        --sz;
    }

    forn(i, 1, sz) c[i + sz] = c[i];
    int ptr = sz + 1;
    while (ptr > 1 && cross(PII(c[ptr - 1].F - a[1].F, c[ptr - 1].S - a[1].S), PII(c[ptr].F - a[1].F, c[ptr].S - a[1].S)) < 0) --ptr;
    while (ptr < 2 * sz && cross(PII(c[ptr + 1].F - a[1].F, c[ptr + 1].S - a[1].S), PII(c[ptr].F - a[1].F, c[ptr].S - a[1].S)) < 0) ++ptr;
    if (ptr > sz) ptr -= sz;
    int ptr2 = 1;
    ll A = 0, ans = 0;
    forn(i, 3, 2 * n) {
        A += abs(cross(PII(a[i].F - a[ptr2].F, a[i].S - a[ptr2].S), PII(a[i - 1].F - a[ptr2].F, a[i - 1].S - a[ptr2].S)));
        while (cross(PII(c[ptr + 1].F - a[i].F, c[ptr + 1].S - a[i].S), PII(c[ptr].F - a[i].F, c[ptr].S - a[i].S)) < 0) {
            ++ptr;
            if (ptr == 2 * sz) ptr -= sz;
        }
        while (ptr2 < i - 1 && cross(PII(a[ptr2].F - a[i].F, a[ptr2].S - a[i].S), PII(c[ptr].F - a[i].F, c[ptr].S - a[i].S)) >= 0) {
            A -= abs(cross(PII(a[ptr2].F - a[i].F, a[ptr2].S - a[i].S), PII(a[ptr2 + 1].F - a[i].F, a[ptr2 + 1].S - a[i].S)));
            ++ptr2;
        }
        ans = max(ans, A);
    }

    cout << ans << "\n";

	return 0;
}

Compilation message

sir.cpp:58:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 49876 KB Output is correct
2 Correct 1 ms 49876 KB Output is correct
3 Correct 0 ms 49876 KB Output is correct
4 Correct 0 ms 49876 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 49876 KB Output is correct
2 Correct 3 ms 49876 KB Output is correct
3 Correct 6 ms 49876 KB Output is correct
4 Correct 3 ms 49876 KB Output is correct
5 Correct 1 ms 49876 KB Output is correct
6 Correct 6 ms 49876 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 49876 KB Output is correct
2 Correct 568 ms 49876 KB Output is correct
3 Correct 439 ms 49876 KB Output is correct
4 Correct 169 ms 49876 KB Output is correct
5 Correct 413 ms 49876 KB Output is correct
6 Correct 455 ms 49876 KB Output is correct