Submission #135459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135459	2019-07-24T05:58:09 Z	이온조(#3249)	Tri (CEOI09_tri)	C++14	50 / 100	124 ms	4072 KB

tri

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define X first
#define Y second
#define sz(V) ((int)V.size())

int CCW(pll A, pll B, pll C) {
	long long tmp = A.X*B.Y + B.X*C.Y + C.X*A.Y - A.Y*B.X - B.Y*C.X - C.Y*A.X;
	if(tmp < 0LL) return -1;
	if(tmp == 0LL) return 0;
	if(tmp > 0LL) return +1;
}

pll add(pll A, pll B, pll C) {
	return {A.X + C.X - B.X, A.Y + C.Y - B.Y};
}

pll P[100009];

int main() {
	int K, M; scanf("%d%d",&K,&M);
	for(int i=1; i<=K; i++) scanf("%lld%lld", &P[i].X, &P[i].Y);
	sort(P+1, P+K+1);
	vector<pll> H;
	for(int i=1; i<=K; i++) {
		while(sz(H) >= 2 && CCW(H[sz(H) - 2], H[sz(H) - 1], P[i]) <= 0) H.pop_back();
		H.push_back(P[i]);
	}
	// puts("HULL");
	// for(auto& it: H) printf("(%lld, %lld)\n", it.X, it.Y);
	// puts("----------------------");
	for(int i=1; i<=M; i++) {
		pll A, B; scanf("%lld%lld%lld%lld", &A.X, &A.Y, &B.X, &B.Y);
		bool f = 0;
		int l = 0, r = sz(H) - 1;
		while(l <= r) {
			int m = l+r >> 1;
			if(H[m].X*A.Y + H[m].Y*B.X <= A.Y*B.X) f = 1;
			if(m+1 == sz(H) || CCW(A, B, add(B, H[m], H[m+1])) == 1) r = m-1;
			else l = m+1;
		}
		if(f) puts("Y");
		else puts("N");
	}
	return 0;
}

Compilation message

tri.cpp: In function 'int main()':
tri.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l+r >> 1;
            ~^~
tri.cpp: In function 'int CCW(pll, pll, pll)':
tri.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
tri.cpp: In function 'int main()':
tri.cpp:23:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int K, M; scanf("%d%d",&K,&M);
            ~~~~~^~~~~~~~~~~~~~
tri.cpp:24:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=K; i++) scanf("%lld%lld", &P[i].X, &P[i].Y);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   pll A, B; scanf("%lld%lld%lld%lld", &A.X, &A.Y, &B.X, &B.Y);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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	380 KB	Output is correct
3	Correct	29 ms	1400 KB	Output is correct
4	Correct	60 ms	2544 KB	Output is correct
5	Correct	124 ms	4072 KB	Output is correct
6	Incorrect	82 ms	2944 KB	Output isn't correct
7	Incorrect	109 ms	3248 KB	Output isn't correct
8	Incorrect	92 ms	3124 KB	Output isn't correct
9	Incorrect	104 ms	3320 KB	Output isn't correct
10	Incorrect	114 ms	3312 KB	Output isn't correct