#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const int inf = 1e9;
const ll inf64 = 1e18;
struct output {
vector<int> res;
void print() {
for (auto x : res) cout << (x ? "Y" : "N") << "\n";
}
bool operator == (const output& o) const {
return res == o.res;
}
};
struct pt {
ll x = 0;
ll y = 0;
pt operator-(const pt& o) const {
return {x - o.x, y - o.y};
}
ll vector_mul(const pt& o) const {
return 1ll * x * o.y - 1ll * o.x * y;
}
bool operator<(const pt& o) const {
return vector_mul(o) > 0;
}
};
ll area(pt a, pt b, pt c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int cmp2(pt a, pt b){
ll val=a.x*b.y-b.x*a.y;
if(val==0)return 0;
if(val<0)return 1;
return -1;
}
const int MAXN = 1e5 + 5;
pt p[MAXN];
struct segtree{
int n;
vector<vector<int>>seg;
bool ans;
void convex_hull(vector<int>&hull,int l,int r){
for(int i=l;i<=r;++i){
while(hull.size()>=2 and area(p[hull[hull.size()-2]],p[hull.back()],p[i])>0)
hull.pop_back();
hull.push_back(i);
}
}
void build(int v,int l, int r){
convex_hull(seg[v],l,r);
if(l==r)return;
int mid=(l+r)>>1;
build(v<<1,l,mid);
build(v<<1|1,mid+1,r);
}
segtree(int xd):n(xd){
seg.resize(n<<2);
build(1,1,n);
}
bool solve(vector<int>&hull,pt a,pt b){
int l=0,r=hull.size()-1;
while(l<r){
int mid=(l+r)>>1;
ll res1=area(a,b,p[hull[mid]]);
if(res1>0)return 1;
ll res2=area(a,b,p[hull[mid+1]]);
if(res1>res2)r=mid-1;
else l=mid+1;
}
return area(a,b,p[hull[l]])>0;
}
void query(int v,int l,int r,pt a,pt b){
if(ans)return;
if(cmp2(b,p[l])<0)return;
if(cmp2(a,p[r])>0)return;
if( cmp2(a,p[l])<=0 and cmp2(p[r],b)<=0 ){
ans|=solve(seg[v],a,b);
return;
}
if(l==r)return;
int mid=(l+r)>>1;
query(v<<1,l,mid,a,b);
query(v<<1|1,mid+1,r,a,b);
}
bool get(pt a,pt b){
ans=0;
query(1,1,n,a,b);
return ans;
}
};
pll intersect_lines(pt L1, pt L2) {
// f(t) = x + t * y
// x1 + t * y1 == x2 + t * t2
// t = (x2 - x1) / (y1 - y2)
ll u = L2.x - L1.x;
ll v = L1.y - L2.y;
if (v < 0) u = -u, v = -v;
return {u, v};
}
bool cmp(pll p1, pll p2) {
return __int128(p1.first) * p2.second < __int128(p2.first) * p1.second;
}
struct CHT {
vector<pt> st;
CHT() = default;
CHT(vector<pt> a) {
sort(a.begin(), a.end(), [&](pt p1, pt p2) {
if (p1.y != p2.y) return p1.y < p2.y;
else return p1.x < p2.x;
});
for (auto p : a) {
if (!st.empty() && st.back().y == p.y) {
st.back().x = p.x;
continue;
}
while ((int) st.size() >= 2) {
pt L1 = st[(int) st.size() - 2];
pt L2 = st[(int) st.size() - 1];
auto x1 = intersect_lines(L1, L2);
auto x2 = intersect_lines(L2, p);
if (cmp(x1, x2)) break;
else st.pop_back();
}
st.push_back(p);
}
}
ll get_max(int p, int q) {
// p * x + q * y -> max
// p > 0
// p * (x + (q / p) * y) -> max
// arg = q / p
assert(p > 0);
pll x0 = {q, p};
int bl = 0, br = (int) st.size(), bm;
while (br - bl > 1) {
bm = bl + (br - bl) / 2;
pll x = intersect_lines(st[bm], st[bm + 1]);
if (cmp(x0, x)) br = bm;
else bl = bm;
}
ll max_value = -8e18;
for (int di = -10; di <= 10; ++di) {
int i = bl + di;
if (i < 0 || i >= (int) st.size()) continue;
ll tmp_value = 1ll * p * st[i].x + 1ll * q * st[i].y;
if (tmp_value > max_value) {
max_value = tmp_value;
}
}
return max_value;
}
};
struct RangeTree {
int n = 0;
vector<vector<pt>> pts;
vector<CHT> cht_xy_pos, cht_xy_neg, cht_yx_pos, cht_yx_neg;
RangeTree(const vector<pt>& a): n(a.size()), pts(4 * n),
cht_xy_pos(4 * n), cht_xy_neg(4 * n), cht_yx_pos(4 * n), cht_yx_neg(4 * n)
{
build(a, 1, 0, n - 1);
}
void build(const vector<pt>& a, int v, int tl, int tr) {
if (tl == tr) {
pts[v].push_back(a[tl]);
} else {
int tm = tl + (tr - tl) / 2;
build(a, v << 1, tl, tm);
build(a, v << 1 | 1, tm + 1, tr);
{
pts[v] = pts[v << 1];
copy(pts[v << 1 | 1].begin(), pts[v << 1 | 1].end(), back_inserter(pts[v]));
}
}
cht_xy_pos[v] = CHT(pts[v]);
for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
cht_xy_neg[v] = CHT(pts[v]);
for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
for (auto& p : pts[v]) swap(p.x, p.y);
cht_yx_pos[v] = CHT(pts[v]);
for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
cht_yx_neg[v] = CHT(pts[v]);
for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
for (auto& p : pts[v]) swap(p.x, p.y);
}
ll get_max(int v, int tl, int tr, int l, int r, int p, int q) {
if (l <= tl && tr <= r) {
if (p > 0) return cht_xy_pos[v].get_max(p, q);
else if (p < 0) return cht_xy_neg[v].get_max(-p, -q);
else {
if (q > 0) return cht_yx_pos[v].get_max(q, p);
else {
assert(q < 0);
return cht_yx_neg[v].get_max(-q, -p);
}
}
} else {
int tm = tl + (tr - tl) / 2;
ll res = -5e18;
if (l <= tm) {
ll tmp = get_max(v << 1, tl, tm, l, r, p, q);
if (tmp > res) res = tmp;
}
if (r > tm) {
ll tmp = get_max(v << 1 | 1, tm + 1, tr, l, r, p, q);
if (tmp > res) res = tmp;
}
return res;
}
}
ll get_max(int l, int r, int p, int q) {
// px + qy -> max
return get_max(1, 0, n - 1, l, r, p, q);
}
};
struct input {
int n, m;
vector<pt> a;
vector<pair<pt, pt>> b;
input() = default;
void read() {
cin >> n >> m;
a.resize(n);
b.resize(m);
for (auto& p : a) cin >> p.x >> p.y;
for (auto& [l, r] : b) {
cin >> l.x >> l.y >> r.x >> r.y;
}
}
void print() {
cout << n << " " << m << "\n";
for (auto p : a) cout << p.x << " " << p.y << "\n";
for (auto [l, r] : b) {
cout << l.x << " " << l.y << " " << r.x << " " << r.y << "\n";
}
}
void gen() {
static mt19937 rnd(42);
const int MAXN = 500;
const int MAXX = 5;
n = rnd() % MAXN + 1;
m = rnd() % MAXN + 1;
a.resize(n);
for (auto& p : a) {
p.x = rnd() % MAXX + 1;
p.y = rnd() % MAXX + 1;
}
b.resize(m);
for (auto& [l, r] : b) {
while (1) {
l.x = rnd() % (MAXX + 1);
l.y = rnd() % (MAXX + 1);
r.x = rnd() % (MAXX + 1);
r.y = rnd() % (MAXX + 1);
if (l.vector_mul(r) == 0) continue;
if (l.x < r.x && l.y <= r.y) continue;
if (l.x > r.x && l.y >= r.y) continue;
int ok = 1;
for (auto p : a) {
if (l.vector_mul(p) == 0 || r.vector_mul(p) == 0 || (r - l).vector_mul(p) == 0) {
ok = 0;
break;
}
}
if (!ok) continue;
break;
}
}
}
void gen_max_test() {
}
output fast() {
sort(a.begin(), a.end(), [&](pt p1, pt p2) {
return p1.vector_mul(p2) > 0;
});
RangeTree rt(a);
vector<int> res;
res.reserve(m);
for (auto [l, r] : b) {
if (l.vector_mul(r) < 0) swap(l, r);
int ql = 1e9, qr = -1e9;
if (l.vector_mul(a.back()) > 0) {
int bl = -1, br = (int) a.size() - 1, bm;
while (br - bl > 1) {
bm = bl + (br - bl) / 2;
if (l.vector_mul(a[bm]) > 0) br = bm;
else bl = bm;
}
ql = br;
}
if (a.front().vector_mul(r) > 0) {
int bl = 0, br = (int) a.size(), bm;
while (br - bl > 1) {
bm = bl + (br - bl) / 2;
if (a[bm].vector_mul(r) > 0) bl = bm;
else br = bm;
}
qr = bl;
}
if (ql <= qr) {
pt v = r - l;
ll tmp = rt.get_max(ql, qr, -v.y, v.x);
ll C = v.vector_mul(l);
res.push_back(tmp > C);
} else {
res.push_back(0);
}
}
return output{res};
}
// #ifdef DEBUG
output slow() {
vector<int> res;
res.reserve(m);
for (auto [l, r] : b) {
if (l.vector_mul(r) < 0) swap(l, r);
int any = 0;
for (auto p : a) {
if (l.vector_mul(p) > 0 && p.vector_mul(r) > 0 && (r - l).vector_mul(p - l) > 0) {
any = 1;
break;
}
}
res.push_back(any);
}
return output{res};
}
// #endif
};
void test_case() {
input in;
in.read();
output res = in.slow();
res.print();
}
void work() {
int t = 1;
#ifdef DEBUG
cin >> t;
#endif
while (t--)
test_case();
}
#ifdef DEBUG
void test() {
for (int t = 1;;t++) {
input in;
in.gen();
input in_fs = in;
input in_sl = in;
output fs = in_fs.fast();
output sl = in_sl.slow();
if (fs == sl) {
cout << "OK" << endl;
fs.print();
cout << "\n=========" << endl;
} else {
cout << "WA " << t << "\n";
cout << "exp\n";
sl.print();
cout << "\n=========\n";
cout << "fnd\n";
fs.print();
cout << "\n=========\n";
in.print();
break;
}
}
}
#endif
#ifdef DEBUG
void max_test() {
input in;
in.gen_max_test();
input in_fs = in;
output fs = in_fs.fast();
fs.print();
}
#endif
signed main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
work();
// test();
// max_test();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |