Submission #848546

# Submission time Handle Problem Language Result Execution time Memory
848546 2023-09-12T21:14:00 Z lovrot Tri (CEOI09_tri) C++17
100 / 100
137 ms 24508 KB
#include <cstdio> 
#include <cassert>
#include <vector>
#include <algorithm> 

#define X first
#define Y second
#define EB emplace_back

using namespace std;

typedef long long ll;

struct dot {
	ll x, y;
	dot() {}
	dot(ll x, ll y) : x(x), y(y) {}
	bool operator< (dot p) { return (p.x - x) * (-y) - (p.y - y) * (-x) > 0; }
	ll operator* (dot p) { return p.x * x + p.y * y; }
};

ll ccw(dot a, dot b, dot c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); }

const int LOG = 17; 
const int N = 1 << LOG;

dot D[N][2], INV[N];
int L[N], R[N], ANS[N];
vector<int> Q[2 * N], I[N]; 
vector<dot> CH, CIR;

int query(const dot &d, int lo, int hi) {
	while(hi - lo > 1) {
		int mi = (lo + hi) / 2;
		if(CH[mi] * d < CH[mi + 1] * d) hi = mi;
		else lo = mi;
	}
	return CH[lo] * d < CH[hi] * d ? lo : hi;
}

void fake() {
	for(dot d : CIR) {
		while(CH.size() > 1 && ccw(end(CH)[-2], end(CH)[-1], d) > 0) CH.pop_back(); 
		CH.EB(d); 
	}
	for(int i : Q[1]) 
		if(ccw(D[i][1], D[i][0], CH[query(INV[i], 0, (int) CH.size() - 1)]) > 0) ANS[i] = 1;
}

void divcon(int lo, int hi, int x = 1) {
	if(lo >= hi || Q[x].empty()) return;
	if(lo + 1 == hi) {
		for(int i : Q[x]) ANS[i] |= ccw(D[i][1], D[i][0], CIR[lo]) > 0;
		return;
	}
	int mi = (lo + hi) / 2;
	for(int i : Q[x]) {
		if(R[i] < mi) Q[2 * x].EB(i); 
		else if(L[i] >= mi) Q[2 * x + 1].EB(i); 
		else I[L[i]].EB(i), I[R[i]].EB(i); 
	}
	CH.clear();	
	for(int i = mi; i < hi; ++i) {
		dot d = CIR[i]; 
		while(CH.size() > 1 && ccw(end(CH)[-2], end(CH)[-1], d) > 0) CH.pop_back(); 
		CH.EB(d); 
		for(int j : I[i])
			if(ccw(D[j][1], D[j][0], CH[query(INV[j], 0, (int) CH.size() - 1)]) > 0) ANS[j] = 1;
	}
	CH.clear();
	for(int i = mi - 1; i >= lo; --i) {
		dot d = CIR[i]; 
		while(CH.size() > 1 && ccw(end(CH)[-2], end(CH)[-1], d) < 0) CH.pop_back(); 
		CH.EB(d); 
		for(int j : I[i])
			if(ccw(D[j][1], D[j][0], CH[query(INV[j], 0, (int) CH.size() - 1)]) > 0) ANS[j] = 1;
	}
	for(int i = lo; i < hi; ++i) I[i].clear();
	divcon(lo, mi, 2 * x); 
	divcon(mi, hi, 2 * x + 1);
}

int search(const dot &d) {
	int lo = -1, hi = (int) CIR.size();
	while(hi - lo > 1) {
		int mi = (lo + hi) / 2;
		if(CIR[mi] < d) lo = mi;
		else hi = mi;
	}
	return hi;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m); 
	for(int i = 0; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y); 
		CIR.EB(dot(x, y)); 
	}
	sort(CIR.begin(), CIR.end()); 
//	for(int i = 0; i < n; ++i) printf("%d %d\n", (int) CIR[i].x, (int) CIR[i].y);
	for(int i = 0; i < m; ++i) {
		int x, y, _x, _y;
		scanf("%d%d%d%d", &x, &y, &_x, &_y); 
		D[i][0] = dot(x, y); 
		D[i][1] = dot(_x, _y); 
		INV[i] = dot(- (D[i][1].y - D[i][0].y), D[i][1].x - D[i][0].x);

		L[i] = search(D[i][1]); 
		R[i] = search(D[i][0]) - 1;
//		printf("%d: %d %d\n", i, L[i], R[i]);
		if(L[i] <= R[i]) Q[1].EB(i);
	}
	divcon(0, n);
	for(int i = 0; i < m; ++i) printf("%c\n", ANS[i] ? 'Y' : 'N');
	return 0;
}

Compilation message

tri.cpp: In function 'int main()':
tri.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
tri.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
tri.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d%d%d%d", &x, &y, &_x, &_y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 3 ms 13660 KB Output is correct
3 Correct 25 ms 16896 KB Output is correct
4 Correct 50 ms 17828 KB Output is correct
5 Correct 98 ms 20460 KB Output is correct
6 Correct 105 ms 20088 KB Output is correct
7 Correct 130 ms 21452 KB Output is correct
8 Correct 103 ms 22308 KB Output is correct
9 Correct 121 ms 23480 KB Output is correct
10 Correct 137 ms 24508 KB Output is correct