oj.uz

답안 #165011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
165011 2019-11-24T16:26:31 Z SpeedOfMagic Meksikanac (COCI16_meksikanac) C++17
20 / 160
 422 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
template<typename T> using v = vector<T>;
//#define int long long
typedef long double ld;
typedef long long ll;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 1'000'000'000'000'000'000;
const long double EPS = 1e-10;
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin >>
#define put fout <<
#else
#define get cin >>
#define put cout <<
#endif
#define eol put endl
void read() {} template<typename A,typename... As> void read (A& a,As&... as){get (a)     ;read(as...) ;}
void print(){} template<typename A,typename... As> void print(A  a,As...  as){put (a)<<" ";print(as...);}
int getInt() { int a; get a; return a; }
mt19937 rng{random_device{}()};
void run();
signed main() { ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(13); run(); }
//code starts here
typedef complex<double> base;
const double PI = acos(-1.0); 
void fft (vector<base> & a, bool invert) {
	int n = (int) a.size();
 
	for (int i=1, j=0; i<n; ++i) {
		int bit = n >> 1;
		for (; j>=bit; bit>>=1)
			j -= bit;
		j += bit;
		if (i < j)
			swap (a[i], a[j]);
	}
 
	for (int len=2; len<=n; len<<=1) {
		double ang = 2*PI/len * (invert ? -1 : 1);
		base wlen (cos(ang), sin(ang));
		for (int i=0; i<n; i+=len) {
			base w (1);
			for (int j=0; j<len/2; ++j) {
				base u = a[i+j],  v = a[i+j+len/2] * w;
				a[i+j] = u + v;
				a[i+j+len/2] = u - v;
				w *= wlen;
			}
		}
	}
	if (invert)
		for (int i=0; i<n; ++i)
			a[i] /= n;
}
void multiply (const vector<int> & a, const vector<int> & b, vector<int> & res) {
	vector<base> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
	size_t n = 1;
	while (n < max (a.size(), b.size()))  n <<= 1;
	n <<= 1;
	fa.resize (n),  fb.resize (n);
 
	fft (fa, false),  fft (fb, false);
	for (size_t i=0; i<n; ++i)
		fa[i] *= fb[i];
	fft (fa, true);
 
	res.resize (n);
	for (size_t i=0; i<n; ++i)
		res[i] = (int) (fa[i].real() + 0.5);
}

// (s1 <-) * (s2 ->) and 0s are required
struct pt {
    int x, y;
};
void run() {
    int n, m;
    read(m, n);
    n++; m++;

    int k;
    get k;
    v<pt> flies(k);
    int K = k; 
    rep(i, 0, k) {
        read(flies[i].x, flies[i].y);
    }

    get k;
    v<pt> pol(k + 1);
    int mnX = m, mnY = n;
    rep(i, 0, k) {
        read(pol[i].x, pol[i].y);
        mnX = min(mnX, pol[i].x);
        mnY = min(mnY, pol[i].y);
    }
    pol[k] = pol[0];

    int lenC = 0, lenR = 0;
    rep(i, 0, k + 1) {
        pol[i].x -= mnX;
        pol[i].y -= mnY;
        lenC = max(lenC, pol[i].x);
        lenR = max(lenR, pol[i].y);
    }
    int prn = n, prm = m;
    m += lenC;
    n += lenR;
    
    vint bitsFlies(n * m, 0);
    rep(i, 0, K) {
        bitsFlies[flies[i].y * m + flies[i].x] = 1;
    }

    char hasPointOnIt[lenC + 1][lenR + 1];
    memset(hasPointOnIt, 0, sizeof hasPointOnIt);
    rep(i, 0, k)
        hasPointOnIt[pol[i].x][pol[i].y] = 1;

    int intersectAfter[lenC + 1][lenR + 1];
    memset(intersectAfter, 0, sizeof intersectAfter);
    rep(i, 0, k) {
        if (pol[i].y == pol[i + 1].y) {
            int dx = (pol[i].x < pol[i + 1].x) ? 1 : -1;
            int px = pol[i].x;
            while (px != pol[i + 1].x) {
                hasPointOnIt[px][pol[i].y] = 1;
                px += dx;
            }
            continue;
        }
        
        int dx = (pol[i].x < pol[i + 1].x) ? 1 : -1;
        int dy = (pol[i].y < pol[i + 1].y) ? 1 : -1;
        if (dy == -1)
            intersectAfter[pol[i].x][pol[i].y]++;
        else
            intersectAfter[pol[i + 1].x][pol[i + 1].y]++;

        int py = pol[i].y;
        int cP = abs(pol[i].x - pol[i + 1].x), cQ = abs(pol[i].y - pol[i + 1].y);
        while (py != pol[i + 1].y) {
            py += dy;
            if (py == pol[i + 1].y)
                break;
            int Dx = dx * (cP * abs(py - pol[i].y) / cQ);
            if (dx == -1)
                Dx = dx * ((cP * abs(py - pol[i].y) + cQ - 1) / cQ);
            if (cP * abs(py - pol[i].y) % cQ == 0)
                hasPointOnIt[pol[i].x + Dx][py] = 1;
            intersectAfter[pol[i].x + Dx][py]++;
        }
    }

    char inPol[lenC + 1][lenR + 1];
    rep(i, 0, lenR + 1) {
//        rep(j, 0, lenC + 1) put char(hasPointOnIt[j][i] + '0');  eol;
        int s = 0;
        for (int j = lenC; j >= 0; --j) {
            s += intersectAfter[j][i];
            intersectAfter[j][i] = s;
            inPol[j][i] = hasPointOnIt[j][i] || s % 2;
        }
    }
    
//eol; rep(i, 0, lenR + 1) { rep(j, 0, lenC + 1) put intersectAfter[j][i]; eol; } eol;
// for (int i = lenR; i >= 0; --i) { rep(j, 0, lenC + 1) put char(inPol[j][i] + '0'); eol; }

    vint bitsPolygon;
    if (lenC + 1 > m || lenR + 1 > n) {
        put 0;
        return;
    }

    for (int x = lenC; x >= 0; --x)
        bitsPolygon.pb(inPol[x][lenR]);
    for (int y = lenR - 1; y >= 0; --y) {
        /*
        rep(x, 0, lenC + 1)
            bitsPolygon.pb(inPol[x][y]);
        rep(x, lenC + 1, m)
            bitsPolygon.pb(0);
        */
        for (int x = m - 1; x >= lenC + 1; --x)
            bitsPolygon.pb(0);
        for (int x = lenC; x >= 0; --x)
            bitsPolygon.pb(inPol[x][y]);
    }
    
  //  cerr << "Length of polygon: lenR = " << lenR << ", lenC = " << lenC << endl;

    vint res;
    multiply(bitsFlies, bitsPolygon, res);
//    rep(i, 0, n * m) put bitsFlies[i]; eol;
//    rep(i, 0, sz(bitsPolygon)) put bitsPolygon[i]; eol;
//    rep(i, 0, sz(res)) put res[i]; eol;
  //  cerr << sz(bitsFlies) << " " << sz(bitsPolygon) << " " << sz(res) << endl;
    int ans = 0;
    vint posPlace;
    rep(i, 0, n)
        rep(j, 0, m)
            posPlace.pb(i < prn && j < prm && i - lenR >= 0 && j - lenC >= 0);
//    for (int i : posPlace)     put i; eol;
    rep(i, 0, sz(posPlace))
        ans += posPlace[i] * (res[i] == 0);
    put ans;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 508 KB Output is correct
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Runtime error 5 ms 732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 235 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 21 ms 2736 KB Output is correct
3 Runtime error 396 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 22 ms 2828 KB Output is correct
3 Runtime error 229 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 504 KB Output is correct
2 Runtime error 233 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 422 ms 39632 KB Output is correct

Subtask #14
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 20388 KB Output is correct

Subtask #16
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)