oj.uz

Submission #243938

# Submission time Handle Problem Language Result Execution time Memory
243938 2020-07-02T09:09:45 Z ne4eHbKa Meksikanac (COCI16_meksikanac) C++17
0 / 160
 1500 ms 1144 KB 
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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 1144 KB Time limit exceeded

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 1120 KB Time limit exceeded

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 928 KB Time limit exceeded

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 512 KB Output isn't correct

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 778 ms 636 KB Output isn't correct

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 1016 KB Time limit exceeded