| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157960 |
2019-10-14T08:43:55 Z |
imyujin |
Tri (CEOI09_tri) |
C++14 |
|
441 ms |
33680 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
const int MAXN = 100010;
const int MX = 1 << 17;
int N, M;
pii dot[MAXN];
pii tri[MAXN][2], p[MAXN];
int qs[MAXN];
vector<int> que[2 * MX];
bool ans[MAXN];
vector<int> ch[2 * MX];
lint cp(pii a, pii b) { return (lint)a.fi * b.se - (lint)a.se * b.fi; }
lint ccw(pii a, pii b, pii c) { return cp(a, b) + cp(b, c) + cp(c, a); }
bool cmp(const pii a, const pii b) { return ccw(pii(0, 0), a, b) > 0; }
int lwb(pii &a) { return lower_bound(dot, dot + N, a, cmp) - dot; }
int upb(pii &a) { return upper_bound(dot, dot + N, a, cmp) - dot; }
pii operator-(pii a, pii b) { return pii(a.fi - b.fi, a.se - b.se); }
void addquery(int idx, int l, int r, int x, int y, int z) {
if(x <= l && r <= y) que[idx].pb(z);
else if(l <= y && x <= r) {
int m = (l + r) / 2;
addquery(idx * 2, l, m, x, y, z);
addquery(idx * 2 + 1, m + 1, r, x, y, z);
}
}
void f(int idx, int l, int r) {
/*
printf("f(idx = %d, l = %d, r = %d)\n", idx, l, r);
printf("que : ");
for(auto a : que[idx]) printf("%d ", a);
puts("");
*/
if(l == r) ch[idx].push_back(l);
else {
int m = (l + r) / 2;
f(idx * 2, l, m);
f(idx * 2 + 1, m + 1, r);
ch[idx].push_back(ch[idx * 2][0]);
int t = 0;
for(int i = 0; i < ch[idx * 2].size(); i++) {
for(; t + 1 < ch[idx * 2 + 1].size(); t++)
if(ccw(dot[ch[idx * 2 + 1][t]], dot[ch[idx * 2][i]], dot[ch[idx * 2 + 1][t + 1]]) > 0)
break;
if(i + 1 == ch[idx * 2].size() || ccw(dot[ch[idx * 2][i]], dot[ch[idx * 2][i + 1]], dot[ch[idx * 2 + 1][t]]) >= 0)
break;
ch[idx].push_back(ch[idx * 2][i + 1]);
}
for(int i = t; i < ch[idx * 2 + 1].size(); i++)
ch[idx].push_back(ch[idx * 2 + 1][i]);
ch[idx * 2].clear();
ch[idx * 2 + 1].clear();
}
int t = 0;
for(auto a : que[idx]) {
while(t + 1 < ch[idx].size() && ccw(tri[a][0], dot[ch[idx][t]], tri[a][1]) >= ccw(tri[a][0], dot[ch[idx][t + 1]], tri[a][1]))
t++;
ans[a] |= ccw(dot[ch[idx][t]], tri[a][0], tri[a][1]) > 0;
}
/*
printf("ch[%d] : ", idx);
for(auto a : ch[idx]) printf("%d ", a);
puts("");
printf("end f(%d)\n", idx);
*/
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
for(int i = 0; i < N; i++) cin >> dot[i].fi >> dot[i].se;
for(int i = 0; i < M; i++) for(int j = 0; j < 2; j++) cin >> tri[i][j].fi >> tri[i][j].se;
sort(dot, dot + N, cmp);
int nn = 0;
for(int i = 0; i < N; i++) {
int mn = i;
for(int j = i + 1; j < N && !ccw(pii(0, 0), dot[i], dot[j]); j++)
if(dot[j].fi < dot[mn].fi) mn = j;
dot[nn++] = dot[mn];
}
N = nn;
for(int i = 0; i < M; i++) {
qs[i] = i;
if(!cmp(tri[i][0], tri[i][1])) swap(tri[i][0], tri[i][1]);
p[i] = tri[i][1] - tri[i][0];
}
sort(qs, qs + M, [&](const int a, const int b) {
if(p[a].se < 0 && p[b].se >= 0) return true;
if(p[a].se >= 0 && p[b].se < 0) return false;
return cmp(p[b], p[a]);
});
for(int i = 0; i < M; i++)
addquery(1, 0, N - 1, lwb(tri[qs[i]][0]), upb(tri[qs[i]][1]) - 1, qs[i]);
f(1, 0, N - 1);
for(int i = 0; i < M; i++) cout << (ans[i] ? "Y" : "N") << "\n";
return 0;
}
Compilation message
tri.cpp: In function 'void f(int, int, int)':
tri.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ch[idx * 2].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~
tri.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; t + 1 < ch[idx * 2 + 1].size(); t++)
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:56:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + 1 == ch[idx * 2].size() || ccw(dot[ch[idx * 2][i]], dot[ch[idx * 2][i + 1]], dot[ch[idx * 2 + 1][t]]) >= 0)
~~~~~~^~~~~~~~~~~~~~~~~~~~~
tri.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = t; i < ch[idx * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(t + 1 < ch[idx].size() && ccw(tri[a][0], dot[ch[idx][t]], tri[a][1]) >= ccw(tri[a][0], dot[ch[idx][t + 1]], tri[a][1]))
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
12920 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12920 KB |
Output is correct |
| 3 |
Correct |
55 ms |
16248 KB |
Output is correct |
| 4 |
Correct |
94 ms |
20112 KB |
Output is correct |
| 5 |
Correct |
178 ms |
26740 KB |
Output is correct |
| 6 |
Correct |
324 ms |
29428 KB |
Output is correct |
| 7 |
Correct |
441 ms |
33680 KB |
Output is correct |
| 8 |
Correct |
292 ms |
28612 KB |
Output is correct |
| 9 |
Correct |
348 ms |
30588 KB |
Output is correct |
| 10 |
Correct |
379 ms |
32084 KB |
Output is correct |
