Submission #157944

#TimeUsernameProblemLanguageResultExecution timeMemory
157944imyujinTri (CEOI09_tri)C++14
0 / 100
408 ms38904 KiB
#include <bits/stdc++.h> using namespace std; typedef long long lint; typedef long double ld; typedef pair<int, int> pii; #define fi first #define se second #define pb push_back const int MAXN = 100010; const int MX = 1 << 17; const pii ori = pii(0, 0); 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(ori, a, b) > 0; }; int lwb(pii &a) { return lower_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(auto a : ch[idx * 2]) if(a != ch[idx * 2].back()) { for(; t + 1 < ch[idx * 2 + 1].size(); t++) if(ccw(dot[ch[idx * 2 + 1][t]], dot[ch[idx * 2][0]], dot[ch[idx * 2 + 1][t + 1]]) >= 0) break; if(ccw(dot[a], dot[a], dot[ch[idx * 2 + 1][t]]) > 0) ch[idx].push_back(a); else break; } 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); 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 false; if(p[a].se >= 0 && p[b].se < 0) return true; return cmp(p[a], p[b]); }); for(int i = 0; i < M; i++) addquery(1, 0, N - 1, lwb(tri[qs[i]][0]), lwb(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 (stderr)

tri.cpp: In function 'void f(int, int, int)':
tri.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; t + 1 < ch[idx * 2 + 1].size(); t++) 
          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = t; i < ch[idx * 2 + 1].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:68: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 timeMemoryGrader output
Fetching results...