Submission #135483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135483	2019-07-24T06:35:37 Z	김세빈(#3248)	Tri (CEOI09_tri)	C++14	100 / 100	206 ms	13080 KB

tri

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct point{
	ll x, y;
	
	point() {}
	point(ll x, ll y) : x(x), y(y) {}
	
	ll sz() { return x * x + y * y; }
	
	ll operator * (point p) { return x * p.y - y * p.x; }
	bool operator == (point p) const { return x * p.y == y * p.x; }
};

ll ccw(point &pa, point &pb, point &pc)
{
	return (pa.x * pb.y + pb.x * pc.y + pc.x * pa.y)
		- (pa.y * pb.x + pb.y * pc.x + pc.y * pa.x);
}

struct query{
	point p1, p2; int i;
	query() {}
	query(point _p1, point _p2, int _i) { p1 = _p1, p2 = _p2, i = _i; }
};

vector <point> P;
vector <query> Q;
int A[101010];
int n, q;

bool check(vector <int> &H, query &k)
{
	ll a, b, c, v, v1, v2;
	int i, s, e, m1, m2;
	
	a = k.p2.y - k.p1.y; b = k.p1.x - k.p2.x;
	c = k.p1.x * k.p2.y - k.p2.x * k.p1.y;
	
	for(s=0, e=H.size()-1; s+4<=e; ){
		m1 = (s + s + e) / 3; v1 = a * P[H[m1]].x + b * P[H[m1]].y;
		m2 = (s + e + e) / 3; v2 = a * P[H[m2]].x + b * P[H[m2]].y;
		if(v1 < v2) e = m2;
		else s = m1;
	}
	
	for(i=s; i<=e; i++){
		v = a * P[H[i]].x + b * P[H[i]].y;
		if(v < c) return 1;
	}
	
	return 0;
}
	
void dnc(int s, int e, vector <int> &X)
{
	if(s > e || X.empty()) return;
	
	vector <int> H, QL, QR, L, R;
	int m = s + e >> 1;
	int i, j;
	
	for(int &t: X){
		if(Q[t].p2 * P[m] > 0) L.push_back(t);
		else if(P[m] * Q[t].p1 > 0) R.push_back(t);
		else{
			QL.push_back(t);
			QR.push_back(t);
		}
	}
	
	sort(QL.begin(), QL.end(), [&](int &qa, int &qb){
		return Q[qa].p1 * Q[qb].p1 < 0;
	});
	
	for(i=m, j=0; i>=s; i--){
		for(; j<QL.size() && P[i] * Q[QL[j]].p1 > 0; j++){
			if(check(H, Q[QL[j]])) A[Q[QL[j]].i] = 1;
		}
		
		for(; H.size() > 1; H.pop_back()){
			if(ccw(P[H[H.size() - 2]], P[H.back()], P[i]) >= 0) break;
		}
		H.push_back(i);
	}
	
	for(; j<QL.size(); j++){
		if(check(H, Q[QL[j]])) A[Q[QL[j]].i] = 1;
	}
	
	H.clear();
	
	sort(QR.begin(), QR.end(), [&](int &qa, int &qb){
		return Q[qa].p2 * Q[qb].p2 > 0;
	});
	
	for(i=m, j=0; i<=e; i++){
		for(; j<QR.size() && P[i] * Q[QR[j]].p2 < 0; j++){
			if(check(H, Q[QR[j]])) A[Q[QR[j]].i] = 1;
		}
		
		for(; H.size() > 1; H.pop_back()){
			if(ccw(P[H[H.size() - 2]], P[H.back()], P[i]) <= 0) break;
		}
		H.push_back(i);
	}
	
	for(; j<QR.size(); j++){
		if(check(H, Q[QR[j]])) A[Q[QR[j]].i] = 1;
	}
	
	dnc(s, m - 1, L); dnc(m + 1, e, R);
}

int main()
{
	vector <int> X;
	ll x, y;
	int i;
	
	scanf("%d%d", &n, &q);
	
	for(i=0; i<n; i++){
		scanf("%lld%lld", &x, &y);
		P.emplace_back(x, y);
	}
	
	sort(P.begin(), P.end(), [&](point &pa, point &pb){
		if(pa.x * pb.y == pa.y * pb.x) return pa.sz() < pb.sz();
		else return pa.x * pb.y > pa.y * pb.x;
	});
	
	P.erase(unique(P.begin(), P.end()), P.end());
	n = P.size();
	
	for(i=0; i<q; i++){
		scanf("%lld%lld", &x, &y); point p1(x, y);
		scanf("%lld%lld", &x, &y); point p2(x, y);
		if(p1 * p2 < 0) swap(p1, p2);
		Q.emplace_back(p1, p2, i);
		X.push_back(i);
	}
	
	dnc(0, n - 1, X);
	
	for(i=0; i<q; i++){
		printf("%c\n", "NY"[A[i]]);
	}
	
	return 0;
}

Compilation message

tri.cpp: In function 'void dnc(int, int, std::vector<int>&)':
tri.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
tri.cpp:81:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<QL.size() && P[i] * Q[QL[j]].p1 > 0; j++){
         ~^~~~~~~~~~
tri.cpp:91:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(; j<QL.size(); j++){
        ~^~~~~~~~~~
tri.cpp:102:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<QR.size() && P[i] * Q[QR[j]].p2 < 0; j++){
         ~^~~~~~~~~~
tri.cpp:112:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(; j<QR.size(); j++){
        ~^~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
tri.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
tri.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &x, &y); point p1(x, y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
tri.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &x, &y); point p2(x, y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	37 ms	3752 KB	Output is correct
4	Correct	84 ms	6524 KB	Output is correct
5	Correct	174 ms	12632 KB	Output is correct
6	Correct	158 ms	11812 KB	Output is correct
7	Correct	204 ms	13080 KB	Output is correct
8	Correct	163 ms	12252 KB	Output is correct
9	Correct	185 ms	12376 KB	Output is correct
10	Correct	206 ms	12924 KB	Output is correct