Submission #717437

#	Time	Username	Problem	Language	Result	Execution time	Memory
717437		maximath_1	Tri (CEOI09_tri)	C++11	100 / 100	329 ms	38072 KiB

tri

#include <bits/stdc++.h>

#define kyou using
#define mo namespace
#define kawaii std

kyou mo kawaii; // hi honey~

#define ll long long
#define ld long double
#define endl "\n"
const int MX = 100005;
const int LG = (int)log2(MX) + 1;
const int BLOCK = 205;
const int inf = 1000000069;
const ll inf_ll = 8000000000000000069ll;
const ll mod = 1e9 + 7;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {0, 1, 0, -1, 0, 0};
const int dy[] = {1, 0, -1, 0, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1}; // 3d
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)

bool untied = 0;
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
	if(!untied) unsyncIO(), untied = 1;
	if(s.size()){
		setIn(s + ".in");
		setOut(s + ".out");
	}
}

struct point{
	ll x, y;

	point& operator-=(const point &a){
    	x -= a.x; y -= a.y;
		return *this; 
	}
	friend point operator-(point a, const point &b){return a -= b;}
};

inline ll cross(point A, point B){
	return A.x * 1ll * B.y - A.y * 1ll * B.x;
}

inline ll mag2(point A){
	return A.x * 1ll * A.x + A.y * 1ll * A.y;
}

int n, q;
vector<point> points;

vector<point> hullify(vector<point> x){
	vector<point> nw;
	for(point i : x){
		if(nw.size() && cross(nw.back(), i) == 0) continue;
		nw.push_back(i);
		while(nw.size() >= 3 && cross(nw[nw.size() - 1] - nw[nw.size() - 2], nw[nw.size() - 2] - nw[nw.size() - 3]) >= 0){
			point tp = nw.back(); nw.pop_back(); nw.pop_back(); 
			nw.push_back(tp);
		}
	}
	return nw;
}

vector<point> st[MX * 4];

void build(int nd, int cl, int cr){
	for(int i = cl; i <= cr; i ++)
		st[nd].push_back(points[i]);
	st[nd] = hullify(st[nd]);
	if(cl != cr){
		build(nd * 2, cl, (cl + cr) / 2);
		build(nd * 2 + 1, (cl + cr) / 2 + 1, cr);
	}
}

bool query(int nd, int cl, int cr, point L, point R){
	if(cross(st[nd].back(), L) < 0 || cross(R, st[nd][0]) < 0) return 0;
	if(cross(L, st[nd][0]) < 0 && cross(st[nd].back(), R) < 0){
		int lf = 0, rg = st[nd].size() - 1;
		for(int md, md2; lf < rg;){
			md = (lf + rg) / 2;
			md2 = md + 1;
			if(cross(R - L, st[nd][md] - L) < cross(R - L, st[nd][md2] - L))
				rg = md;
			else
				lf = md + 1;
		}

		if(cross(R - L, st[nd][lf] - L) < 0) return 1;
		else return 0;
	}

	if(cl != cr){
		bool lf = query(nd * 2, cl, (cl + cr) / 2, L, R);
		bool rg = query(nd * 2 + 1, (cl + cr) / 2 + 1, cr, L, R);
		return (lf | rg);
	}

	return 0;
}

int main(){
	setIO();

	cin >> n >> q;
	points.resize(n);
	for(int i = 0; i < n; i ++)
		cin >> points[i].x >> points[i].y;

	sort(points.begin(), points.end(), [&](point a, point b){
		if(cross(a, b) == 0)
			return mag2(a) < mag2(b);
		return cross(a, b) < 0;
	});

	build(1, 0, n - 1);

	point A, B;
	for(int i = 0; i < q; i ++){
		cin >> A.x >> A.y >> B.x >> B.y;
		if(cross(A, B) > 0) swap(A, B);

		if(query(1, 0, n - 1, A, B)) cout << "Y\n";
		else cout << "N\n";
	}

	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void setIn(std::string)':
tri.cpp:29:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tri.cpp: In function 'void setOut(std::string)':
tri.cpp:30:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100