Submission #40018

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
40018	2018-01-25T10:52:36 Z	krauch	SIR (COI15_sir)	C++14	0 / 100	203 ms	25620 KB

sir

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>

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;
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 b) {
    if (cross(PII(a.F + oo, a.S + oo), PII(b.F + oo, b.S + oo)) != 0) return cross(PII(a.F + oo, a.S + oo), PII(b.F + oo, b.S + oo)) > 0;
    return 1ll * (a.F + oo) * (a.F + oo) + 1ll * (a.S + oo) * (a.S + oo) > 1ll * (b.F + oo) * (b.F + oo) + 1ll * (b.S + oo) * (b.S + oo);
}

int main() {
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

	#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;
    forn(i, 1, m) {
        cin >> b[i].F >> b[i].S;
    }

    sort(b + 1, b + m + 1, cmp);

//    forn(i, 1, m) cerr << b[i].F << " " << b[i].S << "\n";
//    cerr << "\n";

    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;
    }
    reverse(c + 1, c + sz + 1);
    forn(i, 1, sz) c[i + sz] = c[i];

//    forn(i, 1, sz) cerr << c[i].F << " " << c[i].S << "\n";

    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;
}

Subtask #1

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	25620 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	25620 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	203 ms	25620 KB	Output isn't correct
2	Halted	0 ms	0 KB	-