Submission #157477

#	Time	Username	Problem	Language	Result	Execution time	Memory
157477		mosesmayer	Tri (CEOI09_tri)	C++17	0 / 100	72 ms	65540 KiB

tri

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long LL; typedef vector<int> vi; typedef pair<int,int> pii;
template<class F, class S> ostream& operator<< (ostream& os, const pair<F,S> p){os << '{' << p.fi << ", " << p.se << '}'; return os;}

const int INF = 0x3f3f3f3f;

struct Point{
	LL x, y;
	Point(){}
	Point(LL x, LL y): x(x), y(y) {}
	Point operator+ (const Point &rhs) const{
		return Point(x + rhs.x, y + rhs.y);
	}
	Point operator- (const Point &rhs) const{
		return Point(x - rhs.x, y - rhs.y);
	}
	LL operator* (const Point &rhs) const {
		return x * rhs.y - rhs.x * y;
	}
	bool operator< (const Point &rhs) const{
		LL c = x * rhs.y - rhs.x * y;
		return c == 0 ? x < rhs.x : c > 0;
	}
	bool operator> (const Point &rhs) const{
		return rhs < *this;
	}
	bool operator== (const Point &rhs) const{
		return x == rhs.x && y == rhs.y;
	}
};
void operator>> (istream &is, Point &p){
	is >> p.x >> p.y;
}
ostream& operator<< (ostream& os, const Point &p){
	os << '(' << p.x << ", " << p.y << ')';
	return os;
}
LL ccw(Point A, Point B, Point C){
	LL u = (B-A)*(C-A);
	return u == 0 ? 0 : u > 0 ? 1 : -1;
}

int k, m, n;

Point tompel[100500];
pair<Point, Point> tri[100500];

map<Point, int> mp;

bool ans[100500];

namespace RangeTree{
	struct node{
		int lft, rgh;
		vector<Point> hull;
		node():lft(-1), rgh(-1), hull(0) {}
	} tree[2500000];
	int sz = 0;
	void init(){
		tree[sz++] = node();
	}
	void insert(int pos, Point pt, int p, int l, int r){
		if (l == r){
			tree[p].hull.push_back(pt);
			tree[p].hull.push_back(Point(INF,INF));
			return;
		}
		int md = (l + r) >> 1;
		if (pos <= md){
			if (tree[p].lft == -1) tree[p].lft = sz++;
			insert(pos, pt, tree[p].lft, l, md);
		} else {
			if (tree[p].rgh == -1) tree[p].rgh = sz++;
			insert(pos, pt, tree[p].rgh, md+1, r);
		}
	}
	vector<Point> tmp;
	bool andrew(Point x, Point y){
		return x.x == y.x ? x.y < y.y : x.x < y.x;
	}
	void chull(int p, int l, int r){
		if (p == -1) return;
		if (l == r) return;
		int md = (l + r) >> 1;
		chull(tree[p].lft, l, md);
		chull(tree[p].rgh, md+1, r);
		if (tree[p].lft != -1) for (Point &pt : tree[tree[p].lft].hull) tmp.pb(pt);
		if (tree[p].rgh != -1) for (Point &pt : tree[tree[p].rgh].hull) tmp.pb(pt);
		sort(tmp.begin(), tmp.end(), andrew);
		int k = 0;
		for (int i = 0; i < tmp.size(); i++){
			while (k >= 2 && ccw(tree[p].hull[k-2], tree[p].hull[k-1], tmp[i])<=0){
				k--; tree[p].hull.pop_back();
			}
			tree[p].hull.push_back(tmp[i]); k++;
		}
		tmp.clear();
	}

	bool check(Point P, Point Q, Point A, Point B){ // returns if P is higher than Q w.r.t. segment AB
		Point vAB = B - A, vAP = P - A, vAQ = Q - A;
		return vAB * vAP > vAB * vAQ;
	}
	bool query(int i, int j, Point PA, Point PB, int p = 0, int l = 1, int r = n){
		if (p == -1) return 0;
		if (j < l || i > r) return 0;
		if (i <= l && j >= r){
			if (tree[p].hull.empty()) return 0;
			int lo = 0, hi = int(tree[p].hull.size()) - 1, ans = -1;
			while (lo <= hi){
				int md = (lo + hi) >> 1;
				if (check(tree[p].hull[md], tree[p].hull[md+1], PA, PB)){ // if higher then go to right range to get lower
					lo = md + 1;
				} else{
					ans = md; hi = md - 1;
				}
			}
			if (ans == -1) return 0;
			return (PB-PA) * (tree[p].hull[ans]-PA) < 0;
		}
		int md = (l + r) >> 1;
		return query(i, j,PA,PB, tree[p].lft, l, md) || query(i, j,PA,PB, tree[p].rgh, md+1, r);
	}
}

int main(){
	FASTIO;
	cin >> k >> m;
	for (int i = 1; i<= k; i++){
		cin >> tompel[i].x >> tompel[i].y;
		mp[tompel[i]];
	}
	for (int i = 1; i <= m; i++){
		cin >> tri[i].first.x >> tri[i].first.y; cin >> tri[i].second.x >> tri[i].second.y;
		mp[tri[i].first]; mp[tri[i].second];
		if (tri[i].first > tri[i].second) swap(tri[i].first, tri[i].se);
	}
	int cnt = 0;
	for (map<Point, int>::iterator it = mp.begin(); it != mp.end(); it++){
		it -> se = ++cnt;
	}
	n = k + 2 * m;
	RangeTree::init();
	for (int i = 1; i <= k; i++){
		RangeTree::insert(mp[tompel[i]], tompel[i], 0, 1, n);
	}
	RangeTree::chull(0, 1, n);
	for (int i = 1; i <= m; i++){
		ans[i] = RangeTree::query(mp[tri[i].first], mp[tri[i].se], tri[i].se, tri[i].fi);
	}
	for (int i = 1; i <= m; i++)
		cout << (ans[i] ? 'Y' : 'N') << '\n';
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void RangeTree::chull(int, int, int)':
tri.cpp:97:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tmp.size(); i++){
                   ~~^~~~~~~~~~~~

• Subtask 1: 0 / 100