Submission #33956

#	Time	Username	Problem	Language	Result	Execution time	Memory
33956		gs14004	Meksikanac (COCI16_meksikanac)	C++14	160 / 160	513 ms	47388 KiB

meksikanac

#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 (stderr)

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){
                 ^

• 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