Submission #848095

#	Time	Username	Problem	Language	Result	Execution time	Memory
848095		lovrot	Tri (CEOI09_tri)	C++17	50 / 100	86 ms	15436 KiB

tri

#include <cstdio> 
#include <vector> 
#include <algorithm>

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

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

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

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); 
}

dot rotate(dot d) {
	return dot(-d.y, d.x); 
}

int n, m;
pair<dot, dot> D[N];

vector<pair<dot, int>> CIR; 
vector<dot> HLL;

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

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

int ANS[N];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y); 
		CIR.EB(MP(dot(x, y), -1)); 
	}
	for(int i = 0; i < m; ++i) {
		int x, y, x_, y_;
		scanf("%d%d%d%d", &x, &y, &x_, &y_); 
		D[i] = {dot(x, y), dot(x_, y_)}; 
		CIR.EB(MP(dot(x, y), i));
	}
	sort(CIR.begin(), CIR.end()); 
	for(pair<dot, int> &d : CIR) {
		dot p = d.X;
		int ind = d.Y; 
		if(ind == -1) {
			while(HLL.size() > 1 && ccw(end(HLL)[-2], p, end(HLL)[-1]) < 0) HLL.pop_back(); 
			HLL.EB(p);
		} else if(!HLL.empty()) {
			dot p_ = D[ind].Y;
			dot q = rotate(dot(p_.x - p.x, p_.y - p.y));
			dot res = search(q, bound(p_), (int) HLL.size() - 1);
			ANS[ind] = ccw(p_, p, res) > 0;
		}
	}
	for(int i = 0; i < m; ++i) printf("%c\n", ANS[i] ? 'Y' : 'N');
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
tri.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
tri.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d%d%d", &x, &y, &x_, &y_);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 100