Submission #243619

#	Time	Username	Problem	Language	Result	Execution time	Memory
243619		ne4eHbKa	Meksikanac (COCI16_meksikanac)	C++17	0 / 160	158 ms	516 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;
    }
};

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

bs po[N], fl[N];

#define _ <<' '<<

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;

//    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);

    memset(last, -1, sizeof last);

    for(int x = 0; x <= pw; ++x) {
        po[x].reset();
        multiset<ld> v;
        fo(k) {
            pt &a = p[i], &b = p[(i + 1) % k], &c = p[(i + k - 1) % k];
            if(a.x == x && (b.x != x || c.x != x) &&
               (b.x <= x && c.x >= x ||
                b.x >= x && c.x <= x)) v.insert(a.y);
            int lx = a.x, ly = a.y, rx = b.x, ry = b.y;
            if(lx > rx) swap(lx, rx), swap(ly, ry);
            if(lx > x || rx < x) continue;
            if(lx == rx) {
                if(ly > ry) swap(ly, ry);
                for(int y = ly; y <= ry; ++y) po[x].set(y);
                continue;
            }
            ld d = ly + ld((ry - ly) * (x - lx)) / (rx - lx);
            v.insert(d);
        }
        int z = 0; auto it = v.begin();
        for(int y = 0; y <= ph; ++y) {
            bool u = false;
            for(; it != v.end() && *it <= y + eps; ++it) {
                z ^= 1;
                if(abs(*it - y) < eps) u = true;
            }
            if(z + u) po[x].set(y);
        }
    }

    int ans = 0;

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

Compilation message (stderr)

meksikanac.cpp: In function 'void solve()':
meksikanac.cpp:59:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                (b.x <= x && c.x >= x ||
                 ~~~~~~~~~^~~~~~~~~~~

• 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