oj.uz

답안 #135476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135476 2019-07-24T06:27:09 Z 임유진(#3251) Tri (CEOI09_tri) C++14
50 / 100
 110 ms 7112 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

#define fi first
#define se second

const int MAXN = 100005;

lint X[MAXN], Y[MAXN], A[MAXN], B[MAXN];
pll d[MAXN];
int ls[MAXN];
vector<pll> lch, uch;
bool ans[MAXN];

lint cp(pll a, pll b) { return (lint) a.fi * b.se - (lint) a.se * b.fi; }
lint ccw(pll a, pll b, pll c) { return cp(a, b) + cp(b, c) + cp(c, a); }

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int K, M;

	cin >> K >> M;
	for(int i = 0; i < K; i++) cin >> X[i] >> Y[i];
	for(int i = 0; i < M; i++) cin >> d[0].fi >> A[i] >> B[i] >> d[0].se;

	for(int i = 0; i < K; i++) d[i] = make_pair(X[i], Y[i]);
	sort(d, d + K);
	lch.push_back(d[0]);
	for(int i = 1; i < K; i++) {
		while(lch.size() > 1 && ccw(lch[lch.size() - 2], lch.back(), d[i]) <= 0) lch.pop_back();
		lch.push_back(d[i]);
	}
	uch.push_back(d[0]);
	for(int i = 1; i < K; i++) {
		while(uch.size() > 1 && ccw(uch[uch.size() - 2], uch.back(), d[i]) >= 0) uch.pop_back();
		uch.push_back(d[i]);
	}
	for(int i = 0; i < uch.size() / 2; i++) swap(uch[i], uch[uch.size() - i - 1]);
	uch.insert(uch.end(), lch.begin() + 1, lch.end() - 1);
	uch.push_back(uch[0]);
	//for(auto a : uch) printf("(%lld, %lld)\n", a.fi, a.se);

	for(int i = 0; i < M; i++) ls[i] = i;
	sort(ls, ls + M, [&](const int a, const int b) { return B[a] * A[b] < B[b] * A[a]; } );
	//for(int i = 0; i < M; i++) printf("%d ", ls[i]);
	//printf("\n");
	int p = 0;
	for(int i = 1; i < uch.size(); i++)
		if(A[ls[0]] * uch[i].fi + B[ls[0]] * uch[i].se < A[ls[0]] * uch[p].fi + B[ls[0]] * uch[p].se) p = i;
	ans[ls[0]] = A[ls[0]] * uch[p].fi + B[ls[0]] * uch[p].se < A[ls[0]] * B[ls[0]];
	//printf("p = %d\n", p);
	for(int i = 1; i < M; i++) {
		while(p < uch.size() - 1 && A[ls[i]] * uch[p + 1].fi + B[ls[i]] * uch[p + 1].se < A[ls[i]] * uch[p].fi + B[ls[i]] * uch[p].se)
			p++;
		ans[ls[i]] = A[ls[i]] * uch[p].fi + B[ls[i]] * uch[p].se < A[ls[i]] * B[ls[i]];
		//printf("p = %d\n", p);
	}
	
	for(int i = 0; i < M; i++) cout << (ans[i] ? "Y\n" : "N\n");
}

Compilation message

tri.cpp: In function 'int main()':
tri.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < uch.size() / 2; i++) swap(uch[i], uch[uch.size() - i - 1]);
                 ~~^~~~~~~~~~~~~~~~
tri.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < uch.size(); i++)
                 ~~^~~~~~~~~~~~
tri.cpp:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < uch.size() - 1 && A[ls[i]] * uch[p + 1].fi + B[ls[i]] * uch[p + 1].se < A[ls[i]] * uch[p].fi + B[ls[i]] * uch[p].se)
         ~~^~~~~~~~~~~~~~~~

Subtask #1
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 29 ms 1932 KB Output is correct
4 Correct 52 ms 4084 KB Output is correct
5 Correct 103 ms 7112 KB Output is correct
6 Incorrect 84 ms 4728 KB Output isn't correct
7 Incorrect 110 ms 5724 KB Output isn't correct
8 Incorrect 87 ms 4660 KB Output isn't correct
9 Incorrect 102 ms 5368 KB Output isn't correct
10 Incorrect 110 ms 5752 KB Output isn't correct