QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104213 | #6403. Master of Polygon | maroonrk | WA | 124ms | 15300kb | C++20 | 20.1kb | 2023-05-09 14:23:35 | 2023-05-09 14:23:38 |
Judging History
answer
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
//#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
return os<<"{"<<p.a<<","<<p.b<<"}";
}
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
os<<"{";
for(auto e:v)os<<e<<",";
return os<<"}";
}
#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
os<<t<<" ";
dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif
using uint=unsigned;
using ull=unsigned long long;
template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
return os<<vc<t>(all(a));
}
template<int i,class T>
void print_tuple(ostream&,const T&){
}
template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
if(i)os<<",";
os<<get<i>(t);
print_tuple<i+1,T,Args...>(os,t);
}
template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
os<<"{";
print_tuple<0,tuple<Args...>,Args...>(os,t);
return os<<"}";
}
ll read(){
ll i;
cin>>i;
return i;
}
vi readvi(int n,int off=0){
vi v(n);
rep(i,n)v[i]=read()+off;
return v;
}
pi readpi(int off=0){
int a,b;cin>>a>>b;
return pi(a+off,b+off);
}
template<class t>
void print_single(t x,int suc=1){
cout<<x;
if(suc==1)
cout<<"\n";
if(suc==2)
cout<<" ";
}
template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
print_single(p.a,2);
print_single(p.b,suc);
}
template<class T>
void print_single(const vector<T>&v,int suc=1){
rep(i,v.size())
print_single(v[i],i==int(v.size())-1?suc:2);
}
template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
rep(i,v.size())
print_single(v[i]+off,i==int(v.size())-1?suc:2);
}
template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
rep(i,N)
print_single(v[i],i==int(N)-1?suc:2);
}
template<class T>
void print(const T&t){
print_single(t);
}
template<class T,class ...Args>
void print(const T&t,const Args&...args){
print_single(t,2);
print(args...);
}
string readString(){
string s;
cin>>s;
return s;
}
template<class T>
T sq(const T& t){
return t*t;
}
void YES(bool ex=true){
cout<<"YES\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void NO(bool ex=true){
cout<<"NO\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void Yes(bool ex=true){
cout<<"Yes\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void No(bool ex=true){
cout<<"No\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
#ifdef CAPITAL
cout<<"YES"<<"\n";
#else
cout<<"Yes"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void no(bool ex=true){
#ifdef CAPITAL
cout<<"NO"<<"\n";
#else
cout<<"No"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}*/
void possible(bool ex=true){
#ifdef CAPITAL
cout<<"POSSIBLE"<<"\n";
#else
cout<<"Possible"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void impossible(bool ex=true){
#ifdef CAPITAL
cout<<"IMPOSSIBLE"<<"\n";
#else
cout<<"Impossible"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
constexpr ll ten(int n){
return n==0?1:ten(n-1)*10;
}
const ll infLL=LLONG_MAX/3;
#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif
int topbit(signed t){
return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
return __builtin_popcount(t);
}
int popcount(ll t){
return __builtin_popcountll(t);
}
int popcount(ull t){
return __builtin_popcountll(t);
}
int bitparity(ll t){
return __builtin_parityll(t);
}
bool ispow2(int i){
return i&&(i&-i)==i;
}
ll mask(int i){
return (ll(1)<<i)-1;
}
ull umask(int i){
return (ull(1)<<i)-1;
}
ll minp2(ll n){
if(n<=1)return 1;
else return ll(1)<<(topbit(n-1)+1);
}
bool inc(int a,int b,int c){
return a<=b&&b<=c;
}
template<class t> void mkuni(vc<t>&v){
sort(all(v));
v.erase(unique(all(v)),v.ed);
}
ll rand_int(ll l, ll r) { //[l, r]
//#ifdef LOCAL
static mt19937_64 gen;
/*#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif*/
return uniform_int_distribution<ll>(l, r)(gen);
}
ll rand_int(ll k){ //[0,k)
return rand_int(0,k-1);
}
template<class t>
void myshuffle(vc<t>&a){
rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}
template<class t>
int lwb(const vc<t>&v,const t&a){
return lower_bound(all(v),a)-v.bg;
}
template<class t>
bool bis(const vc<t>&v,const t&a){
return binary_search(all(v),a);
}
vvc<int> readGraph(int n,int m){
vvc<int> g(n);
rep(i,m){
int a,b;
cin>>a>>b;
//sc.read(a,b);
a--;b--;
g[a].pb(b);
g[b].pb(a);
}
return g;
}
vvc<int> readTree(int n){
return readGraph(n,n-1);
}
vc<ll> presum(const vi&a){
vc<ll> s(si(a)+1);
rep(i,si(a))s[i+1]=s[i]+a[i];
return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
gnr(i,1,si(a))a[i]-=a[i-1];
return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
int n=si(a),m=si(a[0]);
vvc<ll> b(n+1,vc<ll>(m+1));
rep(i,n)rep(j,m)
b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
return b;
}
//verify してないや
void transvvc(int&n,int&m){
swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
assert(si(a)==n);
vvc<t> b(m,vi(n));
rep(i,n){
assert(si(a[i])==m);
rep(j,m)b[j][i]=a[i][j];
}
a.swap(b);
transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
assert(si(a)==n);
vvc<t> b(m,vi(n));
rep(i,n){
assert(si(a[i])==m);
rep(j,m)b[m-1-j][i]=a[i][j];
}
a.swap(b);
rotvvc(n,m,args...);
}
//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
int n=si(a);
vi idx(n);iota(all(idx),0);
sort(all(idx),[&](int i,int j){return a[i]<a[j];});
return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
int n=si(a);
assert(si(idx)==n);
vc<t> vs(n);
rep(i,n)vs[i]=a[idx[i]];
return vs;
}
//CF850C
vi invperm(const vi&p){
int n=si(p);
vi q(n);
rep(i,n)q[p[i]]=i;
return q;
}
template<class t,class s=t>
s SUM(const vc<t>&a){
return accumulate(all(a),s(0));
}
template<class t>
t MAX(const vc<t>&a){
return *max_element(all(a));
}
template<class t>
t MIN(const vc<t>&a){
return *min_element(all(a));
}
template<class t,class u>
pair<t,u> operator+(const pair<t,u>&a,const pair<t,u>&b){
return mp(a.a+b.a,a.b+b.b);
}
vi vid(int n){
vi res(n);iota(all(res),0);
return res;
}
template<class S>
S getrev(S s){
reverse(all(s));
return s;
}
pi operator+(pi a,pi b){return pi(a.a+b.a,a.b+b.b);}
template<class t>
t gpp(vc<t>&vs){
assert(si(vs));
t res=move(vs.back());
vs.pop_back();
return res;
}
//copied from yosupo's library
//ptARTLY VERIFIED
//USACO 2022 January ptlatinum C
//#define GEOF
#ifdef GEOF
using ld=long double;
//using ld=double;
const ld PI=acos(ld(-1));
#else
using ld=int;
#endif
const ld eps=1e-9;
int sgn(ld a){return a<-eps?-1:(a>eps?1:0);}
int sgn(ld a,ld b){return sgn(a-b);}
/*
using pt=complex<ld>;
#define x real()
#define y imag()
*/
struct pt {
ld x,y;
//pt(ld _x = ld(0), ld _y = ld(0)) : x(_x), y(_y) {}
pt():x(0),y(0){}
pt(ld xx,ld yy):x(xx),y(yy){}
pt operator+(const pt& r) const { return {x + r.x, y + r.y}; }
pt operator-(const pt& r) const { return {x - r.x, y - r.y}; }
pt operator*(const pt& r) const {
return {x * r.x - y * r.y, x * r.y + y * r.x};
}
pt inv()const{
ld d=norm();
return {x/d,-y/d};
}
pt operator/(const pt&r)const{
return operator*(r.inv());
}
pt operator*(const ld& r) const { return {x * r, y * r}; }
pt operator/(const ld& r) const { return {x / r, y / r}; }
pt& operator+=(const pt& r) { return *this = *this + r; }
pt& operator-=(const pt& r) { return *this = *this - r; }
pt& operator*=(const pt& r) { return *this = *this * r; }
pt& operator/=(const pt& r) { return *this = *this / r; }
pt& operator*=(const ld& r) { return *this = *this * r; }
pt& operator/=(const ld& r) { return *this = *this / r; }
pt operator-() const { return {-x, -y}; }
static int cmp(const pt&a,const pt&b){
int v=sgn(a.x,b.x);
return v?v:sgn(a.y,b.y);
}
bool operator<(const pt& r) const {
return cmp(*this,r)<0;
}
bool operator<=(const pt& r) const {
return cmp(*this,r)<=0;
}
bool operator>(const pt& r) const {
return cmp(*this,r)>0;
}
bool operator==(const pt& r) const { return sgn((*this - r).rabs()) == 0; }
bool operator!=(const pt& r) const { return !(*this == r); }
ld norm() const { return x * x + y * y; }
ld rabs() const { return max(std::abs(x), std::abs(y)); } // robust abs
pair<ld, ld> to_pair() const { return {x, y}; }
#ifdef GEOF
ld abs() const { return sqrt(norm()); }
ld arg() const { return atan2(y, x); }
static pt polar(ld le, ld th) { return {le * cos(th), le * sin(th)}; }
#endif
};
istream& operator>>(istream& is, pt& p){
return is>>p.x>>p.y;
}
ostream& operator<<(ostream& os, const pt& p) {
return os << "pt(" << p.x << ", " << p.y << ")";
}
ld norm(const pt&a){
return a.norm();
}
#ifdef GEOF
ld abs(const pt&a){
return sqrt(norm(a));
}
//XXII Opencup Gpt of Ural K
pt normalized(const pt&a){
return a/abs(a);
}
ld arg(const pt&a){return a.arg();}
//normalize to [-PI,PI)
//Contest 2: ptKU Contest 1, ptTZ Summer 2022 Day 4
ld normarg(ld a){
ld res=fmod(a+PI,2*PI);
if(res<0)res+=PI;
else res-=PI;
return res;
}
//AOJ1183
//arg between ab
//assume given lengths are valid
ld arg(ld a,ld b,ld c){
return acos(min(max((a*a+b*b-c*c)/(2*a*b),ld(-1)),ld(1)));
}
#endif
ld norm(const pt&a,const pt&b){
return (a-b).norm();
}
ld dot(const pt&a,const pt&b){return a.x*b.x+a.y*b.y;}
ld crs(const pt& a,const pt& b){return a.x*b.y-a.y*b.x;}
ld crs(const pt& a,const pt& b,const pt& c){return crs(b-a,c-a);}
int ccw(const pt& a,const pt& b){return sgn(crs(a,b));}
int ccw(const pt& a,const pt& b,const pt& c){return ccw(b-a,c-a);}
//(-pi,0](0,pi]
int argtype(const pt&a){
if(sgn(a.y)==0)return a.x<0?1:0;
return a.y<0?0:1;
}
int argcmp(const pt&a,const pt&b){
int at=argtype(a),bt=argtype(b);
if(at!=bt)return at<bt?-1:1;
return -ccw(a,b);
};
bool argless(const pt&a,const pt&b){return argcmp(a,b)<0;}
//(-2)[a,-1](0)[b,1](2)
int bet(pt a,pt b,pt c){
pt d=b-a;
ld e=dot(d,c-a);
if(sgn(e)<=0)return sgn(e)-1;
return sgn(e-norm(d))+1;
}
//AOJ0153
//三角形 abc に d が含まれるか?0-no,1-edge,2-in
int cont(pt a,pt b,pt c,pt d){
if(ccw(a,b,c)==-1) swap(b,c);
return min({ccw(a,b,d),ccw(b,c,d),ccw(c,a,d)})+1;
}
//(a,b) を結ぶ直線を考え,x 座標との交点の y 座標を求める
//(分子,分母)を返す
pair<ld,ld> xcut(const pt&a,const pt&b,ld x){
return mp(a.y*(b.x-x)-b.y*(a.x-x),b.x-a.x);
}
//XXII Opencup Gpt of Ural K
pt rot90(pt a){
return pt(-a.y,a.x);
}
#ifdef GEOF
ld xcutval(const pt&a,const pt&b,ld x){
auto [p,q]=xcut(a,b,x);
return p/q;
}
//AOJ1183
//Xmas2010 E
//-+ の 順で返す
//a の符号により,small/large が決まる
int qeq(ld a,ld b,ld c,ld&d,ld&e){
if(sgn(a)==0){
if(sgn(b)==0)return 0;
d=-c/b;
return 1;
}
ld f=b*b-4*a*c;
if(sgn(f)<0)return 0;
ld g=sqrt(max(f,ld(0)));
d=(-b-g)/(2*a);
e=(-b+g)/(2*a);
return sgn(f)+1;
}
#else
pt normdir(pt a){
if(a==pt(0,0))return a;
int g=gcd(a.x,a.y);
return pt(a.x/g,a.y/g);
}
#endif
ld area2(const vc<pt>&ps){
ld res=0;
rep(i,si(ps))res+=crs(ps[i],ps[(i+1)%si(ps)]);
return res;
}
//The 1st Universal Cup. Stage 15: Hangzhou J
struct F{
ld a,b;
F():a(0),b(1){}
F(ld aa,ld bb):a(aa),b(bb){}
F(pair<ld,ld> ab):F(ab.a,ab.b){}
static int cmp(const F&a,const F&b){
assert(a.b>=0);
assert(b.b>=0);
if(a.b==0&&b.b==0){
assert(a.a!=0);
assert(b.a!=0);
return int(a.a>0)-int(b.a>0);
}
//using T=__int128;
using T=ll;
T c=(T)a.a*b.b;
T d=(T)b.a*a.b;
return c<d?-1:c==d?0:1;
}
F operator-()const{return F{-a,b};}
bool operator<(const F&r)const{
return cmp(*this,r)<0;
}
bool operator<=(const F&r)const{
return cmp(*this,r)<=0;
}
bool operator>(const F&r)const{
return cmp(*this,r)>0;
}
bool operator>=(const F&r)const{
return cmp(*this,r)>=0;
}
bool operator==(const F&r)const{
return cmp(*this,r)==0;
}
bool operator!=(const F&r)const{
return cmp(*this,r)!=0;
}
};
const F Finf{1,0};
//max huld
//有理数で全てを計算する
//The 1st Universal Cup. Stage 15: Hangzhou J
//Author: Simon Lindholm
//https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h
struct Line {
mutable ld a,b;
mutable F p;
bool operator<(const Line& o) const { return a < o.a; }
bool operator<(F x) const { return p<x;}
};
struct LineContainer:multiset<Line,less<>>{
F div(ld a,ld b){return b<0?F{-a,-b}:F{a,b};}
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = Finf; return false; }
if (x->a == y->a) x->p = x->b > y->b ? Finf : -Finf;
else x->p = div(y->b - x->b, x->a - y->a);
return x->p>=y->p;
}
void add(ld a, ld b) {
auto z = insert({a, b, F()}), 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));
}
//x の分母が非負でないと壊れるだろうね
//例えば (a,b) を add して,(pa+qb) の max を取りたい,みたいなクエリを考える
//q>=0 ならば p/q をqueryすることで解決
ld query(F x){
assert(x.b>=0);
//assert(!empty());
if(empty())return -inf;
auto l = *lower_bound(x);
return l.a * x.a + l.b * x.b;
}
};
//F は linecontainer_frac から引っ張ってこようね
//(x,y)->(x+y*eps,y) と変形してあると思い込む
//2 つの線分が占める x 座標の範囲に正の共通部分があるとする
//The 1st Universal Cup. Stage 15: Hangzhou J
struct S{
//多分線分同士が端点以外で交わらないというケースだけ動くコード
//線分に接するみたいな状況が発生すると話が変わってきてしまう
pt a,b;
S(){}
S(const pt&aa,const pt&bb):a(min(aa,bb)),b(max(aa,bb)){assert(a<b);}
bool operator<(const S&r)const{
if(a==r.a)return ccw(a,b,r.b)>0;
else if(a<r.a)return ccw(a,b,r.a)>0;
else return ccw(r.a,r.b,a)<0;
}
F evaly(pt x)const{
if(!(a<=x&&x<=b))exit(0);
assert(a<=x&&x<=b);
if(a.x==b.x)return F{x.y,1};
else return xcut(a,b,x.x);
}
//値が 4 乗程度になりがち
static int cmp(const S&a,const S&b,pt x){
return F::cmp(a.evaly(x),b.evaly(x));
}
bool operator<(const pair<S,pt>&r)const{
return cmp(*this,r.a,r.b)<0;
}
};
void slv(){
int n,q;cin>>n>>q;
vc<pt> ps(n);
rep(i,n)cin>>ps[i];
rotate(ps.bg,min_element(all(ps)),ps.ed);
auto xy=ps;sort(all(xy));
pt xymin=xy[0],xymax=xy[n-1];
vc<S> qs(q);
rep(i,q){
pt a,b;cin>>a>>b;
qs[i]=S(a,b);
}
vi ans(q);
rep(i,q){
auto&[a,b]=qs[i];
if(bis(xy,a)||bis(xy,b))ans[i]=1;
}
rep(i,q)if(ans[i]==0){
auto [a,b]=qs[i];
xy.pb(max(xymin,min(a,xymax)));
xy.pb(max(xymin,min(b,xymax)));
}
mkuni(xy);
int s=si(xy)-1;
struct Q{
F v;
int i;
bool operator<(const Q&r)const{
if(v!=r.v)return v<r.v;
else return i<r.i;
}
};
vc<Q> w[2][2];
auto getseg=[&](int i){
pt a=ps[i],b=ps[(i+1)%n];
if(a>b)swap(a,b);
return S(a,b);
};
vc<S> ss;
LineContainer lc;
auto dfs=[&](auto self,int l,int r,vi pid,vi qid)->void{
if(pid.empty()||qid.empty())return;
//pid の各区間は [xy[l],xy[r]] と正の交わりを持つ
//qid の各区間は [xy[l],xy[r]] と正の交わりを持つ
ss.clear();
rep(i,2)rep(j,2)w[i][j].clear();
for(int i=0;i<si(pid);){
auto [a,b]=getseg(pid[i]);
if(a<=xy[l]&&xy[r]<=b){
ss.eb(a,b);
i++;
}else{
int j=i+1;
while(j<si(pid)){
auto [c,d]=getseg(pid[j]);
if(c<=xy[l]||xy[r]<=d)break;
j++;
}
assert(j<si(pid));
F lmin=Finf,lmax=-Finf;
F rmin=Finf,rmax=-Finf;
auto upd=[&](S t){
if(t.a<=xy[l]){
assert(t.b<xy[r]);
auto v=t.evaly(xy[l]);
chmin(lmin,v);
chmax(lmax,v);
}else{
assert(xy[r]<=t.b);
auto v=t.evaly(xy[r]);
chmin(rmin,v);
chmax(rmax,v);
}
};
upd(getseg(pid[i]));
upd(getseg(pid[j]));
if(lmin<=lmax){
rng(k,i+1,j+1)w[0][0].pb({lmin,pid[k]});
rng(k,i+1,j+1)w[0][1].pb({lmax,pid[k]});
}
if(rmin<=rmax){
rng(k,i+1,j+1)w[1][0].pb({rmin,pid[k]});
rng(k,i+1,j+1)w[1][1].pb({rmax,pid[k]});
}
i=j+1;
}
}
sort(all(ss));
for(auto i:qid)if(ans[i]==0){
auto getid=[&](pt v){
auto j=lower_bound(all(ss),mp(qs[i],v));
if(j!=ss.ed&&S::cmp(*j,qs[i],v)==0)
ans[i]=1;
return j;
};
if(getid(max(qs[i].a,xy[l]))!=getid(min(qs[i].b,xy[r])))
ans[i]=1;
}
rep(lr,2)rep(ud,2){
if(w[lr][ud].empty())continue;
bool has=false;
for(auto i:qid)if(ans[i]==0){
auto [a,b]=qs[i];
if(a<=xy[l]&&xy[r]<=b){
auto v=qs[i].evaly(lr==0?xy[l]:xy[r]);
w[lr][ud].pb({v,inf+i});
has=true;
}
}
if(!has)continue;
if(ud)for(auto&[v,i]:w[lr][ud])v.a=-v.a;
sort(all(w[lr][ud]));
lc.clear();
F pre=-Finf;
for(auto [v,i]:w[lr][ud]){
if(i<inf){
pt a=ps[i];
if(ud)a.y=-a.y;
lc.add(a.x,a.y);
pre=v;
}else{
i-=inf;
if(pre==v)ans[i]=1;
else{
auto [a,b]=qs[i];
if(ud){
a.y=-a.y;
b.y=-b.y;
}
pt dir=rot90(b-a);
ll val=lc.query(F(dir.x,dir.y));
if(dot(a,dir)<=val)ans[i]=1;
}
}
}
}
if(r-l>1){
vi pl,pr,ql,qr;
int m=(l+r)/2;
for(auto i:pid){
auto [a,b]=getseg(i);
if(a<=xy[l]&&xy[r]<=b)continue;
if(a<xy[m])pl.pb(i);
if(xy[m]<b)pr.pb(i);
}
for(auto i:qid)if(ans[i]==0){
auto [a,b]=qs[i];
if(a<=xy[l]&&xy[r]<=b)continue;
if(a<xy[m])ql.pb(i);
if(xy[m]<b)qr.pb(i);
}
self(self,l,m,pl,ql);
self(self,m,r,pr,qr);
}
};
dfs(dfs,0,s,vid(n),vid(q));
rep(i,q){
if(ans[i])YES(0);
else NO(0);
}
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
//int t;cin>>t;rep(_,t)
slv();
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3552kb
input:
4 6 1 1 4 1 4 4 1 4 0 2 2 0 0 1 1 1 0 0 5 5 2 2 4 2 2 2 3 2 5 1 0 2
output:
YES YES YES YES NO YES
result:
ok 6 token(s): yes count is 5, no count is 1
Test #2:
score: -100
Wrong Answer
time: 124ms
memory: 15300kb
input:
20 200000 8838 9219 12190 11292 15953 7581 16690 6159 21104 5484 8978 1076 4354 1065 1261 676 12684 14159 15469 22416 13493 28027 15531 26837 18253 26053 26444 24253 22160 19958 24879 12856 28793 22156 25300 10245 14749 15078 12946 13942 26544 28338 18806 21279 5592 29200 20935 25253 28189 17513 215...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements