제출 #456194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456194		grt	Zvijezda (COCI19_zvijezda)	C++17	20 / 110	1093 ms	4500 KiB

zvijezda

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Point {
	ll x, y;
};

const int nax = 1e5 + 10;
int t, n, q;
Point p[nax];

__int128 det(Point a, Point b, Point c) {
	return (__int128)(b.x - a.x) * (c.y - a.y) - (__int128)(c.x - a.x) * (b.y - a.y);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t >> n;
	for(int i = 0; i < n; ++i) {
		cin >> p[i].x >> p[i].y;
	}
	int cnt = 0;
	cin >> q;
	while(q--) {
		ll a, b;
		cin >> a >> b;
		a ^= (ll)cnt * cnt * cnt * t;
		b ^= (ll)cnt * cnt * cnt * t;
		bool sign = det(p[0], p[1], {a, b}) >= 0;
		int r = 0;
		for(int i = 1; i < n; ++i) {
			if((det(p[i], p[(i + 1) % n], {a, b}) >= 0) == sign) {
				r = i;
			} else {
				break;
			}
		}
		int l = 0;
		for(int i = n - 1; i >= 1; --i) {
			if((det(p[i], p[(i + 1) % n], {a, b}) >= 0) == sign) {
				l = i;
			} else {
				break;
			}
		}
		bool w = false;
		if(r == n - 1) {
			if(sign) w = true;
		} else {
			if(sign) {
				if(((n - l) % n) + r + 1 > n / 2) w = true;
			} else {
				if(((n - l) % n) + r + 1 < n / 2) w = true;
			}
		}
		cnt += w;
		if(w) cout << "DA\n";
		else cout << "NE\n";
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60