#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 505;
const int MAXC = 1<<10;
const int MAXM = 10005;
typedef complex<double> base;
void fft(vector<base> &a, bool inv){
int n = a.size(), j = 0;
vector<base> roots(n/2);
for(int i=1; i<n; i++){
int bit = (n >> 1);
while(j >= bit){
j -= bit;
bit >>= 1;
}
j += bit;
if(i < j) swap(a[i], a[j]);
}
double ang = 2 * acos(-1) / n * (inv ? -1 : 1);
for(int i=0; i<n/2; i++){
roots[i] = base(cos(ang * i), sin(ang * i));
}
for(int i=2; i<=n; i<<=1){
int step = n / i;
for(int j=0; j<n; j+=i){
for(int k=0; k<i/2; k++){
base u = a[j+k], v = a[j+k+i/2] * roots[step * k];
a[j+k] = u+v;
a[j+k+i/2] = u-v;
}
}
}
if(inv) for(int i=0; i<n; i++) a[i] /= n;
}
lint ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
bool mid(int s, int x, int e){
if(s > e) swap(s, e);
return s < x && x < e;
}
int n, m, k;
pi v[MAXM];
int chk1[MAXC][MAXC]; // flies
int chk2[MAXC][MAXC]; // point in polygon
int conv[MAXC][MAXC];
pi solve(pi s, pi e, int x){
if(s > e) swap(s, e);
pi ans = pi(abs(x - s.first), abs(e.first - s.first));
ans.first *= e.second - s.second;
ans.first += ans.second * s.second;
return ans;
}
void point_in_polygon(){
for(int i=0; i<=n; i++){
vector<pi> crs;
for(int j=0; j<k; j++){
if(mid(v[j].first, i, v[j+1].first)) crs.push_back(solve(v[j], v[j+1], i));
if(v[j+1].first == i && mid(v[j].first, i, v[j+2].first)){
crs.push_back(pi(v[j+1].second, 1));
continue;
}
if(v[j].first != i && v[j+1].first == i){
bool ok = 1;
if(v[j].first < i && v[j+2].first <= i && ccw(v[j+1], v[j], v[j+2]) > 0){
ok = 0;
}
if(v[j].first > i && v[j+2].first >= i && ccw(v[j+1], v[j], v[j+2]) > 0){
ok = 0;
}
if(ok) crs.push_back(pi(v[j+1].second, 1));
}
if(v[j+1].first == i && v[j+2].first != i){
bool ok = 1;
if(v[j].first < i && v[j+2].first <= i && ccw(v[j+1], v[j], v[j+2]) > 0){
ok = 0;
}
if(v[j].first > i && v[j+2].first >= i && ccw(v[j+1], v[j], v[j+2]) > 0){
ok = 0;
}
if(ok) crs.push_back(pi(v[j+1].second, 1));
}
}
sort(crs.begin(), crs.end(), [&](const pi &a, const pi &b){
return 1ll * a.first * b.second < 1ll * b.first * a.second;
});
assert(crs.size() % 2 == 0);
for(int j=0; j<crs.size(); j+=2){
// printf("[%d/%d %d/%d] ", crs[j].first, crs[j].second, crs[j+1].first, crs[j+1].second);
int curv = (crs[j].first + crs[j].second - 1) / crs[j].second;
while(curv * crs[j+1].second <= crs[j+1].first) chk2[i][curv++] = 1;
}
// puts("");
}
}
vector<base> b1[MAXC], b2[MAXC];
void convolute(){
for(int i=0; i<MAXC; i++){
b1[i].resize(MAXC);
b2[i].resize(MAXC);
for(int j=0; j<MAXC; j++){
b1[i][j] = chk1[i][j];
b2[i][j] = chk2[i][j];
}
}
for(int i=0; i<MAXC; i++){
fft(b1[i], 0);
fft(b2[i], 0);
}
for(int i=0; i<MAXC; i++){
vector<base> p1(MAXC), p2(MAXC);
for(int j=0; j<MAXC; j++){
p1[j] = b1[j][i];
p2[j] = b2[j][i];
}
fft(p1, 0);
fft(p2, 0);
for(int i=0; i<MAXC; i++) p1[i] *= p2[i];
fft(p1, 1);
for(int j=0; j<MAXC; j++) b1[j][i] = p1[j];
}
for(int i=0; i<MAXC; i++) fft(b1[i], 1);
for(int i=0; i<MAXC; i++){
for(int j=0; j<MAXC; j++){
conv[i][j] = (int)round(b1[i][j].real());
}
}
}
int main(){
int q;
cin >> n >> m >> q;
while(q--){
int x, y;
cin >> x >> y;
chk1[x][y] = 1;
}
int minx = 1e9, maxx = -1e9;
int miny = 1e9, maxy = -1e9;
cin >> k;
for(int i=0; i<k; i++){
cin >> v[i].first >> v[i].second;
minx = min(minx, v[i].first);
maxx = max(maxx, v[i].first);
miny = min(miny, v[i].second);
maxy = max(maxy, v[i].second);
}
if(maxx - minx > n || maxy - miny > m){
cout << 0;
return 0;
}
for(int i=0; i<k; i++){
v[i].first -= minx;
v[i].second -= miny;
}
lint ans = 0;
for(int i=2; i<k; i++) ans += ccw(v[0], v[i-1], v[i]);
if(ans < 0) reverse(v, v + k);
v[k] = v[0];
v[k+1] = v[1];
point_in_polygon();
int dx = (maxx - minx), dy = (maxy - miny);
for(int i=0; i<dx-i; i++){
for(int j=0; j<=dy; j++){
swap(chk2[i][j], chk2[dx-i][j]);
}
}
for(int i=0; i<=dx; i++) reverse(chk2[i], chk2[i] + dy + 1);
convolute();
ans = 0;
for(int i=0; i<=n-dx; i++){
for(int j=0; j<=m-dy; j++){
if(conv[i+dx][j+dy] == 0) ans++;
}
}
cout << ans;
}
Compilation message
meksikanac.cpp: In function 'void point_in_polygon()':
meksikanac.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<crs.size(); j+=2){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
14480 KB |
Output is correct |
| 2 |
Correct |
469 ms |
47388 KB |
Output is correct |
| 3 |
Correct |
443 ms |
47388 KB |
Output is correct |
| 4 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
486 ms |
47388 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
14484 KB |
Execution killed because of forbidden syscall gettid (186) |
