Submission #135518

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135518	2019-07-24T07:26:03 Z	송준혁(#3252)	Tri (CEOI09_tri)	C++14	50 / 100	139 ms	7928 KB

tri

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;

int N, Q;
pii P[101010];
vector<pii> UCH, LCH;

LL CCW(pii a, pii b, pii c){
	pii p = pii(b.first-a.first, b.second-a.second);
	pii q = pii(c.first-a.first, c.second-a.second);
	return p.first*q.second - p.second*q.first;
}

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++) scanf("%d %d", &P[i].first, &P[i].second);
	sort(P+1, P+N+1);
	for (int i=1; i<=N; i++){
		while (LCH.size() > 1 && CCW(LCH[LCH.size()-2], LCH[LCH.size()-1], P[i]) <= 0) LCH.pop_back();
		LCH.push_back(P[i]);
	}
	for (int i=1; i<=N; i++){
		while (UCH.size() > 1 && CCW(UCH[UCH.size()-2], UCH[UCH.size()-1], P[i]) >= 0) UCH.pop_back();
		UCH.push_back(P[i]);
	}
	while (Q--){
		LL a, b, Min=1ll<<60, Max=-(1ll<<60);
		scanf("%*d %lld %lld %*d", &a, &b);
		int L=0, R=LCH.size()-1;
		while (L <= R){
			int m1 = L+(R-L)/3;
			int m2 = L+(R-L)/3*2;
			LL r1 = LCH[m1].second*b + a*LCH[m1].first - a*b;
			LL r2 = LCH[m2].second*b + a*LCH[m2].first - a*b;
			Min = min(Min, r1), Min = min(Min, r2);
			if (r1 < r2) R = m2 - 1;
			else L = m1 + 1;
		}

		L=0, R=UCH.size()-1;
		while (L <= R){
			int m1 = L+(R-L)/3;
			int m2 = L+(R-L)/3*2;
			LL r1 = UCH[m1].second*b + a*UCH[m1].first - a*b;
			LL r2 = UCH[m2].second*b + a*UCH[m2].first - a*b;
			Max = max(Max, r1), Max = max(Max, r2);
			if (r1 > r2) R = m2 - 1;
			else L = m1 + 1;
		}
		if (Min > 0 || Max < 0) puts("N");
		else puts("Y");
	}
	return 0;
}

Compilation message

tri.cpp: In function 'int main()':
tri.cpp:18:67: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  for (int i=1; i<=N; i++) scanf("%d %d", &P[i].first, &P[i].second);
                                          ~~~~~~~~~~~              ^
tri.cpp:18:67: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
tri.cpp:17: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:18:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%d %d", &P[i].first, &P[i].second);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%*d %lld %lld %*d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	31 ms	1912 KB	Output is correct
4	Correct	72 ms	3820 KB	Output is correct
5	Correct	139 ms	6992 KB	Output is correct
6	Incorrect	85 ms	5868 KB	Output isn't correct
7	Incorrect	113 ms	7672 KB	Output isn't correct
8	Incorrect	99 ms	6392 KB	Output isn't correct
9	Incorrect	109 ms	7160 KB	Output isn't correct
10	Incorrect	122 ms	7928 KB	Output isn't correct