#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);
char flies2[m][n];
memset(flies2, 0, sizeof flies2);
int K = k;
rep(i, 0, k) {
read(flies[i].x, flies[i].y);
flies2[flies[i].x][flies[i].y] = 1;
}
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;
if (lenC + 1 > prm || lenR + 1 > prn) {
put 0;
return;
}
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;
}
hasPointOnIt[pol[i + 1].x][pol[i + 1].y] = 1;
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;
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]);
}
int ans = 0;
for (int y = 0; y + lenR < prn; ++y)
for (int x = 0; x + lenC < prm; ++x) {
for (int dx = 0; dx < lenC + 1; ++dx)
for (int dy = 0; dy < lenR + 1; ++dy)
if (bitsFlies[(y + dy) * m + x + dx] && inPol[dx][dy])
goto nxt;
//cout << x << " " << y << endl;
ans++;
nxt:;
}
put ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
552 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
952 ms |
3060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
540 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
2296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
900 KB |
Output isn't correct |
