| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 543595 |
2022-03-30T23:52:21 Z |
jacynkaa |
Tri (CEOI09_tri) |
C++17 |
|
610 ms |
65536 KB |
#include <bits/stdc++.h>
#include <chrono>
#include <math.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
#ifdef LOCAL
ostream &operator<<(ostream &out, string str) {
for (char c : str)
out << c;
return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << '{';
for (auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) \
{}
#endif
//#define int long long
typedef double ld;
namespace CNT {
struct Line {
mutable ld k, m, p;
bool operator<(const Line &o) const { return k < o.k; }
bool operator<(ld x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// ( for doubles , use i n f = 1/.0 , div (a , b) = a/b)
const double inf = 1 / .0;
ld div(ld a, ld b) { // floored division
return a / b;
}
bool isect(iterator x, iterator y) {
if (y == end()) {
x->p = inf;
return false;
}
if (x->k == y->k)
x->p = x->m > y->m ? inf : -inf;
else
x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ld k, ld m) {
auto z = insert({k, -m, 0}), y = z++, x = y;
while (isect(y, z))
z = erase(z);
if (x != begin() && isect(--x, y))
isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
pii query(ld x) {
assert(!empty());
auto l = *lower_bound(x);
return mp(l.k, -l.m);
}
};
} // namespace CNT
namespace GEO {
typedef long double K;
const K EPS = 1e-9;
struct xy { // punkt w 2D
K x, y;
xy(K xi, K yi) : x(xi), y(yi) {}
xy(pii X) : x(X.st), y(X.nd) {}
xy() {}
K norm() const { return x * x + y * y; } // kwadrat(!) normy euklidesowej
pii getP() { return {x, y}; }
};
typedef xy P;
xy operator+(xy a, xy b) { return xy(a.x + b.x, a.y + b.y); }
xy operator-(xy a, xy b) { return xy(a.x - b.x, a.y - b.y); }
xy operator*(xy a, K f) { return xy(a.x * f, a.y * f); }
xy operator/(xy a, K f) { return xy(a.x / f, a.y / f); }
xy cross(xy a) { return xy(-a.y, a.x); } // obrot o 90 stopni
K operator*(xy a, xy b) { return a.x * b.x + a.y * b.y; }
K det(xy a, xy b) { return a.x * b.y - b.x * a.y; }
// mowi czy jak bylismy w X, jestesmy w Y i bedziemy w Z to skrecamy w lewo(right-prawo)
bool left(xy X, xy Y, xy Z) { return det(Y - X, Z - Y) > EPS; }
bool right(xy X, xy Y, xy Z) { return det(Y - X, Z - Y) < -EPS; }
struct line { // prosta {v: n*v=c} (n - wektor normalny)
P n;
K c;
line(P ni, K ci) : n(ni), c(ci) {}
line() {}
};
// Czy punkt lezy na prostej?
bool on_line(P a, line p) { return fabs(p.n * a - p.c) < EPS; }
// Prosta przechodzaca przez 2 punkty ccw. Zalozenie: a!=b
line span(P a, P b) { return line(cross(b - a), det(b, a)); }
// Symetralna odcinka. Zalozenie: a!=b
line median(P a, P b) { return line(b - a, (b - a) * (b + a) * 0.5); }
// Przeciecie 2 prostych
P intersection(line p, line q) {
K d = det(p.n, q.n);
if (fabs(d) < EPS)
throw "rownolegle";
return cross(p.n * q.c - q.n * p.c) / d;
}
// Prosta rownolegla przechodzaca przez punkt
line parallel(P a, line p) { return line(p.n, p.n * a); }
// Prosta prostopadla przechodzaca przez punkt
line perp(P a, line p) { return line(cross(p.n), det(p.n, a)); }
// Odleglosc punktu od prostej
K dist(P a, line p) { return fabs(p.n * a - p.c) / sqrt(p.n.norm()); }
K dist(P a, P b) {
P tmp = a - b;
return sqrt(tmp.x * tmp.x + tmp.y * tmp.y);
}
// Rzut prostokatny punktu na prosta
P proj(P a, line p) { return a + p.n * ((p.c - p.n * a) / p.n.norm()); }
struct AngleCmp {
xy root;
AngleCmp(const xy &root_ = xy(0, 0)) : root(root_) {}
void makeSure(const xy &a) const { assert(a.x > EPS || a.x < -EPS || a.y > EPS || a.y < -EPS); }
int hp(const xy &a) const { return a.y < -EPS || (a.y <= EPS && a.x < -EPS); }
bool operator()(xy a, xy b) const {
a = a - root;
makeSure(a);
b = b - root;
makeSure(b);
int cmpHP = hp(a) - hp(b);
if (cmpHP)
return cmpHP < 0;
K d = det(a, b);
if (d > EPS || d < -EPS)
return d > 0;
return a.norm() < b.norm() - EPS;
}
};
} // namespace GEO
namespace ST {
#define r1 ((l + r) / 2) // ulatwia branie srodka przedzialu
#define l2 (r1 + 1) // same
const int MAXN = 1e5 + 99;
bool tab[MAXN];
pair<pii, pii> Z[MAXN];
bool ans(pii A, pii B, CNT::LineContainer &L, vector<pii> &punkty) {
int dif_x = (A.st - B.st);
int dif_y = (A.nd - B.nd);
debug(A, B, dif_x, dif_y);
if (dif_x == 0)
return punkty[0].st <= A.st;
ld R = ld(dif_y) / ld(dif_x);
debug(R);
auto p = L.query(R);
debug(p);
return GEO::right(GEO::xy(A), GEO::xy(B), GEO::xy(p));
}
struct SegmentTree { // drzewo przedział-przedział (add,sum) nie ma pewnosci ze dziala
struct content {
CNT::LineContainer L;
vector<pii> punkty;
vector<int> zapytania;
};
vector<content> C;
int size;
SegmentTree(int x) {
size = (1 << (32 - __builtin_clz(x)));
C.resize(size * 2);
}
void solve(int i) {
for (int x : C[i].zapytania) {
debug(x);
bool res = ans(Z[x].st, Z[x].nd, C[i].L, C[i].punkty);
tab[x] = res ? true : tab[x];
}
C[i].zapytania.clear();
C[i].L.clear();
}
void solve(vector<pii> &P) {
rep(i, 2 * size) C[i].zapytania.shrink_to_fit();
rep(i, sz(P)) {
C[i + size].punkty.push_back(P[i]);
C[i + size].L.add(P[i].st, P[i].nd);
solve(i + size);
}
for (int i = size - 1; i > 0; i--) {
for (auto p : C[2 * i].punkty) {
C[i].punkty.push_back(p);
C[i].L.add(p.st, p.nd);
}
for (auto p : C[2 * i + 1].punkty) {
C[i].punkty.push_back(p);
C[i].L.add(p.st, p.nd);
}
sort(all(C[i].punkty));
solve(i);
C[2 * i + 1].punkty.clear();
C[2 * i].punkty.clear();
}
}
void query(int p, int q, int val, int l, int r, int wezel = 1) { // suma na przedzial [p,q]
if (p > q)
return;
if (p == l && q == r) {
C[wezel].zapytania.push_back(val);
return;
}
query(p, min(r1, q), val, l, r1, 2 * wezel);
query(max(l2, p), q, val, l2, r, 2 * wezel + 1);
}
void query(int p, int q, int val) { query(p, q, val, 0, size - 1); }
}; // namespace ST
} // namespace ST
int32_t main() {
_upgrade;
int k, m;
cin >> k >> m;
vector<GEO::xy> V;
rep(i, k) {
int x, y;
cin >> x >> y;
V.push_back({x, y});
}
sort(all(V), GEO::AngleCmp());
ST::SegmentTree D(k + 1);
rep(j, m) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
GEO::xy X1 = {x1, y1};
GEO::xy X2 = {x2, y2};
auto q = upper_bound(all(V), X1, GEO::AngleCmp()) - V.begin();
auto p = upper_bound(all(V), X2, GEO::AngleCmp()) - V.begin();
if (p == q)
continue;
if (p > q) {
swap(p, q);
swap(X1, X2);
}
q--;
ST::Z[j] = {X1.getP(), X2.getP()};
debug(x1, y1, x2, y2, p, q);
D.query(p, q, j);
}
vector<pii> R(k);
rep(i, k) R[i] = {V[i].x, V[i].y};
V.clear();
debug(R);
D.solve(R);
rep(i, m) cout << (ST::tab[i] ? "Y" : "N") << endl;
}
Compilation message
tri.cpp: In function 'int32_t main()':
tri.cpp:262:20: warning: narrowing conversion of 'x' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
262 | V.push_back({x, y});
| ^
tri.cpp:262:23: warning: narrowing conversion of 'y' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
262 | V.push_back({x, y});
| ^
tri.cpp:271:21: warning: narrowing conversion of 'x1' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
271 | GEO::xy X1 = {x1, y1};
| ^~
tri.cpp:271:25: warning: narrowing conversion of 'y1' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
271 | GEO::xy X1 = {x1, y1};
| ^~
tri.cpp:272:21: warning: narrowing conversion of 'x2' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
272 | GEO::xy X2 = {x2, y2};
| ^~
tri.cpp:272:25: warning: narrowing conversion of 'y2' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
272 | GEO::xy X2 = {x2, y2};
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| 3 |
Correct |
94 ms |
15720 KB |
Output is correct |
| 4 |
Correct |
202 ms |
30016 KB |
Output is correct |
| 5 |
Correct |
412 ms |
59904 KB |
Output is correct |
| 6 |
Correct |
483 ms |
58064 KB |
Output is correct |
| 7 |
Correct |
610 ms |
65536 KB |
Output is correct |
| 8 |
Correct |
464 ms |
57176 KB |
Output is correct |
| 9 |
Correct |
529 ms |
60796 KB |
Output is correct |
| 10 |
Correct |
591 ms |
64552 KB |
Output is correct |
