| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 135476 |
2019-07-24T06:27:09 Z |
임유진(#3251) |
Tri (CEOI09_tri) |
C++14 |
|
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)
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
