Submission #251336

#	Time	Username	Problem	Language	Result	Execution time	Memory
251336		VEGAnn	Meksikanac (COCI16_meksikanac)	C++14	160 / 160	296 ms	8952 KiB

meksikanac

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define ft first
#define sd second
#define i2 pair<int,int>
#define i4 pair<i2,i2>
using namespace std;
typedef long double ld;
const int root = 31;
const int md = 998244353;
const int oo = 2e9;
const int MX = 510;
const int N = MX * MX; // 255k (?)
const int K = 10010;
const ld E = 1e-9;
const int PW = 24;
vector<int> flies, poly, res;
vector<i4> seg;
int xf[N], yf[N], xp[K], yp[K], xb, yb, n, k, ans, roots[PW];
bool inside[MX][MX];

void BAD(){
    cout << 0;
    exit(0);
}

ld get_cord(i4 fi, ld cr_x){
    return ld(fi.ft.sd) + (ld)(fi.sd.sd - fi.ft.sd) * (ld)(cr_x - fi.ft.ft) / (ld)(fi.sd.ft - fi.ft.ft);
}

int area(i2 p1, i2 p2, i2 p3){
    return (p2.ft - p1.ft) * (p3.sd - p1.sd) - (p2.sd - p1.sd) * (p3.ft - p1.ft);
}

struct cmp{
    bool operator()(const i4 &fi, const i4 &se) const {
        if (fi.ft == se.ft){
            return area(fi.sd, fi.ft, se.sd) < 0;
        } else if (fi.sd == se.sd){
            return area(fi.ft, fi.sd, se.ft) > 0;
        } else {
            ld cr_x = max(fi.ft.ft, se.ft.ft);

            ld y_fi = get_cord(fi, cr_x);
            ld y_se = get_cord(se, cr_x);

            return y_fi < y_se;
        }
    }
};

set<i4, cmp> events;
set<i4, cmp>::iterator iter;

void get_points(){
    int mx = oo, my = oo;

    for (int i = 0; i < k; i++){
        mx = min(mx, xp[i]);
        my = min(my, yp[i]);
    }

    for (int i = 0; i < k; i++){
        xp[i] -= mx;
        yp[i] -= my;

        if (xp[i] > xb || yp[i] > yb)
            BAD();

        inside[xp[i]][yp[i]] = 1;
    }

    for (int i = 0; i < k; i++){
        int nt = (i + 1) % k;

        if (xp[i] == xp[nt]){
            int fr = min(yp[i], yp[nt]);
            int to = max(yp[i], yp[nt]);

            for (int j = fr; j <= to; j++)
                inside[xp[i]][j] = 1;
        } else {
            seg.PB({{xp[i], yp[i]}, {xp[nt], yp[nt]}});

            seg.PB({{xp[nt], yp[nt]}, {xp[i], yp[i]}});
        }
    }

    sort(all(seg));

    for (int x_cr = 0, id = 0; x_cr <= xb; x_cr++){
        int j = id;

        while (j < sz(seg) && seg[j].ft.ft == x_cr){
            if (seg[j].ft < seg[j].sd)
                events.insert(seg[j]);
            else {
                swap(seg[j].ft, seg[j].sd);
                events.erase(seg[j]);
            }

            j++;
        }

        if (sz(events) > 0){
            iter = events.begin();

            ld cord = get_cord(*iter, x_cr);

            int par = 1;

            for (iter = next(iter); iter != events.end(); iter = next(iter), par ^= 1) {
                ld nw_cd = get_cord(*iter, x_cr);

                if (par){
                    int fr = (int)ceil(cord - E);
                    int to = (int)trunc(nw_cd + E);

                    for (int it = fr; it <= to; it++)
                        inside[x_cr][it] = 1;
                }

                cord = nw_cd;
            }
        }

        id = j;
    }
}

int mult(int x, int y) { return (1ll * x * y) % md; }

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int binpow(int x, int po){
    int res = 1;
    while (po > 0){
        if (po & 1)
            res = mult(res, x);
        x = mult(x, x);
        po >>= 1;
    }
    return res;
}

void fft(vector<int> &a, int po){
    if (po == 0) return;

    int siz = (1 << po);
    int hlf = (siz >> 1);

    vector<int> a0(hlf), a1(hlf);

    for (int i = 0, j = 0; i < siz; i += 2, j++){
        a0[j] = a[i];
        a1[j] = a[i + 1];
    }

    fft(a0, po - 1);
    fft(a1, po - 1);

    int fi = 1, se = roots[1];

    for (int i = 0; i < hlf; i++){
        a[i] = sum(a0[i], mult(a1[i], fi));
        a[i + hlf] = sum(a0[i], mult(a1[i], se));

        fi = mult(fi, roots[po]);
        se = mult(se, roots[po]);
    }
}

vector<int> multiply(vector<int> &a, vector<int> &b){
    int po = 0;

    while (max(sz(a), sz(b)) >= (1 << (po + 1)))
        po++;

    po++;

    while (sz(a) < (1 << po)) a.PB(0);
    while (sz(b) < (1 << po)) b.PB(0);

    fft(a, po);
    fft(b, po);

    for (int i = 0; i < sz(a); i++)
        a[i] = mult(a[i], b[i]);

    fft(a, po);

    reverse(a.begin() + 1, a.end());

    int inv = binpow(sz(a), md - 2);

    for (int i = 0; i < sz(a); i++)
        a[i] = mult(a[i], inv);

    return a;
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    roots[PW - 1] = root;

    for (int po = PW - 2; po >= 0; po--)
        roots[po] = mult(roots[po + 1], roots[po + 1]);

    cin >> xb >> yb >> n;

    for (int i = 0; i < n; i++)
        cin >> xf[i] >> yf[i];

    cin >> k;

    for (int i = 0; i < k; i++)
        cin >> xp[i] >> yp[i];

    get_points();

    int mem_x = (1 + yb) * 2, mem_wh = mem_x * (xb + 1);
    int Mx = -oo, My = -oo;

    for (int i = 0; i < k; i++){
        Mx = max(Mx, xp[i]);
        My = max(My, yp[i]);
    }

    flies.resize(mem_wh);
    poly.resize(mem_wh);

    for (int x = 0; x <= xb; x++)
    for (int y = 0; y <= yb; y++)
        if (inside[x][y])
            poly[x * mem_x + y] = 1;

    for (int i = 0; i < n; i++)
        flies[mem_wh - 1 - (xf[i] * mem_x + yf[i])] = 1;

    res = multiply(flies, poly);

    for (int x = 0; x <= xb; x++)
    for (int y = 0; y <= yb; y++)
        if (res[mem_wh - 1 - (x * mem_x + y)] == 0 && x + Mx <= xb && y + My <= yb)
            ans++;

    cout << ans;

    return 0;
}

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