Submission #243938

#	Time	Username	Problem	Language	Result	Execution time	Memory
243938		ne4eHbKa	Meksikanac (COCI16_meksikanac)	C++17	0 / 160	1590 ms	1144 KiB

meksikanac

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

#define fo(x) for(int i = 0; i < x; ++i)
#define no return void(cout << "0\n")

template<typename t> void umin(t &a, t b) {a = min(a, b);}
template<typename t> void umax(t &a, t b) {a = max(a, b);}

typedef long double ld;

const int N = 505;
const int K = 10005;
const int oo = 1e9 + 5;
const ld eps = 1e-12;

typedef bitset<N> bs;

struct pt {
    int x, y;
    void read() {
        cin >> x >> y;
    }
};

struct line {
    ld a, b, c;
    line() {};
    line(pt p, pt q):
        a(p.y - q.y),
        b(q.x - p.x) {
            c = -a * p.x
                -b * p.y;
        }
    pair<ld, ld> operator& (const line &f) const {
        if(a * f.b == f.a * b) return {-1, -1};
        return {
            -
            (c * f.b - f.c * b) /
            (a * f.b - f.a * b),
            -
            (a * f.c - f.a * c) /
            (a * f.b - f.a * b)
        };
    }
};

int fh, fw, ph, pw, n, k, mn, mx;
pt f[N * N], p[K];

line lp[K];

bs po[N], fl[N];

#define _ <<' '<<

inline bool inr(ld t, int l, int r) { return l > r ? t + eps > r && t - eps < l
                                                   : t + eps > l && t - eps < r; }

void solve() {
    cin >> fw >> fh >> n;
    fo(n) f[i].read();
    cin >> k;
    fo(k) p[i].read();

    mn = +oo; fo(k) umin(mn, p[i].x); fo(k) p[i].x -= mn;
    mn = +oo; fo(k) umin(mn, p[i].y); fo(k) p[i].y -= mn;

    pw = 0; fo(k) umax(pw, p[i].x); if(pw > fw) no;
    ph = 0; fo(k) umax(ph, p[i].y); if(ph > fh) no;

    fo(k) lp[i] = line(p[i], p[(i + 1) % k]);

//    for(int i = 0; i < k; ++i) cerr << p[i].x _ p[i].y << endl;

    fo(fw + 1) fl[i].reset();
    fo(n) fl[f[i].x].set(f[i].y);

    for(int x = 0; x <= pw; ++x) {
        for(int y = 0; y <= ph; ++y) {
            line z({x, y}, {x + (int)2e6, y - 1});
            int f {};
            for(int i = 0; i < k; ++i) {
                ld xx, yy;
                tie(xx, yy) = z & lp[i];
                if(xx + eps > x && inr(xx, p[i].x, p[(i + 1) % k].x)
                                && inr(yy, p[i].y, p[(i + 1) % k].y)) f ^= 1;
            }
            if(f) po[x].set(y);
        }
    }

    for(int i = 0; i < k; ++i) po[p[i].x].set(p[i].y);

    int ans = 0;

//    for(int x = 0; x <= pw; ++x) {
//        for(int y = 0; y <= ph; ++y) cerr << po[x][y];
//        po[x].reset();
//        cerr << endl;
//    }
//    for(int i = 0; i < k; ++i) po[p[i].x].set(p[i].y); cerr << endl;
//    for(int x = 0; x <= pw; ++x) {
//        for(int y = 0; y <= ph; ++y) cerr << po[x][y];
//        cerr << endl;
//    }

    for(int dx = 0; pw + dx <= fw; ++dx) {
        for(int dy = 0; ph + dy <= fh; ++dy) {
            for(int x = 0; x <= pw; ++x)
                if((po[x] << dy & fl[x + dx]).any()) goto bad;
            ++ans;
            bad:;
        }
    }

    cout << ans << endl;
}

int main() {
    cerr.precision(2); cerr << fixed;
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    for(int i = 1; i <= t; ++i) {
        cerr << "case #" << i << endl;
        solve();
        cerr << endl;
    }
#else
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
#endif // _LOCAL
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10