QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#315892 | #8168. Spacecraft | ucup-team087# | AC ✓ | 735ms | 4952kb | C++20 | 23.3kb | 2024-01-27 16:21:38 | 2024-01-27 16:21:39 |
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);
}
template<class t> bool isuni(vc<t> v){
int s=si(v);
mkuni(v);
return si(v)==s;
}
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,class u>
int lwb(const vc<t>&v,const u&a){
return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&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);
}
template<class t>
vc<t> presum(const vc<t>&a){
vc<t> s(si(a)+1);
rep(i,si(a))s[i+1]=s[i]+a[i];
return s;
}
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,size_t K,class s=t>
s SUM(const array<t,K>&a){
return accumulate(all(a),s(0));
}
template<class t>
t MAX(const vc<t>&a){
return *max_element(all(a));
}
template<class t>
pair<t,int> MAXi(const vc<t>&a){
auto itr=max_element(all(a));
return mp(*itr,itr-a.bg);
}
template<class A>
auto MIN(const A&a){
return *min_element(all(a));
}
template<class t>
pair<t,int> MINi(const vc<t>&a){
auto itr=min_element(all(a));
return mp(*itr,itr-a.bg);
}
vi vid(int n){
vi res(n);iota(all(res),0);
return res;
}
template<class S>
void soin(S&s){
sort(all(s));
}
template<class S,class F>
void soin(S&s,F&&f){
sort(all(s),forward<F>(f));
}
template<class S>
S soout(S s){
soin(s);
return s;
}
template<class S>
void rein(S&s){
reverse(all(s));
}
template<class S>
S reout(S s){
rein(s);
return s;
}
template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a){return mp(-a.a,-a.b);}
template<class t,class u>
istream&operator>>(istream&is,pair<t,u>&a){
return is>>a.a>>a.b;
}
template<class t>
t gpp(vc<t>&vs){
assert(si(vs));
t res=move(vs.back());
vs.pop_back();
return res;
}
template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
a.insert(a.ed,all(b));
}
template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
(pb(a,forward<Args>(b)),...);
return a;
}
template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
for(auto&v:a)v+=x;
return a;
}
template<class t,class u>
vc<t> operator+(vc<t> a,u x){
return a+=x;
}
template<class t>
vc<t> operator+(const vc<t>&a,const vc<t>&b){
vc<t> c(max(si(a),si(b)));
rep(i,si(a))c[i]+=a[i];
rep(i,si(b))c[i]+=b[i];
return c;
}
template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
for(auto&v:a)v-=x;
return a;
}
template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
return a-=x;
}
template<class t,class u>
void remval(vc<t>&a,const u&v){
a.erase(remove(all(a),v),a.ed);
}
//消した要素の個数を返してくれる
//UCUP 2-8-F
template<class t,class F>
int remif(vc<t>&a,F f){
auto itr=remove_if(all(a),f);
int res=a.ed-itr;
a.erase(itr,a.ed);
return res;
}
template<class VS,class u>
void fila(VS&vs,const u&a){
fill(all(vs),a);
}
template<class t,class u>
int findid(const vc<t>&vs,const u&a){
auto itr=find(all(vs),a);
if(itr==vs.ed)return -1;
else return itr-vs.bg;
}
template<class t>
void rtt(vc<t>&vs,int i){
rotate(vs.bg,vs.bg+i,vs.ed);
}
//copied from yosupo's library
//PARTLY 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=ll;
#endif
const ld eps=1e-12;
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()
*/
namespace geo2d{
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();
}
ld rabs(const pt&a){
return a.rabs();
}
#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;
}
//normalize to [0,2*PI)
//Multiuni2023-10-E
ld normarg_nonnegative(ld a){
ld res=fmod(a,2*PI);
if(res<0)res+=2*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;
}
using ln=pair<pt,pt>;
pt dir(ln a){return a.b-a.a;}
pt eval(ln a,ld b){return a.a+dir(a)*b;}
ld crs(ln a,pt b){return crs(a.a,a.b,b);}
int ccw(ln a,pt b){return ccw(a.a,a.b,b);}
int bet(ln a,pt b){return bet(a.a,a.b,b);}
ld projt(ln a,pt b){
pt c=dir(a);
return dot(c,b-a.a)/norm(c);
}
pt proj(ln a,pt b){
pt c=dir(a);
return a.a+c*dot(c,b-a.a)/norm(c);
}
pt refl(ln a,pt b){
return proj(a,b)*2-b;
}
//AOJ1157
//0-no,1-yes(endpoint),2-yes(innner),3-overelap
//if the two line touch like this
// x----x----x
//it returns 1
int iss(ln a,ln b){
int c1=ccw(a.a,a.b,b.a),c2=ccw(a.a,a.b,b.b);
int d1=ccw(b.a,b.b,a.a),d2=ccw(b.a,b.b,a.b);
if(c1||c2||d1||d2)return 1-max(c1*c2,d1*d2);
int f=bet(a.a,a.b,b.a),g=bet(a.a,a.b,b.b);
if(max(f,g)==-2||min(f,g)==2)return 0;
if(max(f,g)==-1||min(f,g)==1)return 1;
return 3;
}
//segment a intersects line b?
//endpoints inclusive
bool isl(ln a,ln b){
int d1=ccw(b.a,b.b,a.a),d2=ccw(b.a,b.b,a.b);
return d1*d2<=0;
}
//並行でない->true, というだけ
//直線が一致とかは考えてないことに注意
bool ill(ln a,ln b){
return ccw(dir(a),dir(b));
}
ld cllt(ln a,ln b){
return crs(b.a,b.b,a.a)/crs(dir(a),dir(b));
}
//ICPC Yokohama 2022 J
pair<ld,ld> clltf(ln a,ln b){
return mp(crs(b.a,b.b,a.a),crs(dir(a),dir(b)));
}
//AOJ1033
pt cll(ln a,ln b){
return eval(a,crs(b.a,b.b,a.a)/crs(dir(a),dir(b)));
}
vc<pt> halfpint(vc<ln> s){
sort(all(s),[&](ln a,ln b){
int c=argcmp(dir(a),dir(b));
if(c)return c<0;
return ccw(b,a.a)>0;
});
s.erase(unique(all(s),[&](ln a,ln b){
return argcmp(dir(a),dir(b))==0;
}),s.ed);
int n=si(s);
vi cur;
rep(ii,n*2){
int i=ii%n,m;
while((m=si(cur))>=2){
if(ccw(s[i],cll(s[cur[m-2]],s[cur[m-1]]))>0)break;
cur.pop_back();
}
cur.pb(i);
}
vi cnt(n);
for(auto i:cur)cnt[i]++;
vc<ln> t;
rep(i,n)if(cnt[i]==2)t.pb(s[i]);
int m=si(t);
vc<pt> res(m);
rep(i,m)res[i]=cll(t[i],t[(i+1)%m]);
return res;
}
}
//VERIFY: yosupo
//KUPC2017J
//AOJDSL1A
//without rank
struct unionfind{
vi p,s;
int c;
unionfind(int n):p(n,-1),s(n,1),c(n){}
void clear(){
fill(all(p),-1);
fill(all(s),1);
c=si(p);
}
int find(int a){
return p[a]==-1?a:(p[a]=find(p[a]));
}
//set b to a child of a
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b)return false;
p[b]=a;
s[a]+=s[b];
c--;
return true;
}
bool same(int a,int b){
return find(a)==find(b);
}
int sz(int a){
return s[find(a)];
}
};
bool dbg=false;
/*
using ld=long double;
const ld eps=1e-12;
int sgn(ld a){return a<-eps?-1:(a>eps?1:0);}
int sgn(ld a,ld b){return sgn(a-b);}
*/
//ll で verify (TTPC2022 N)
//frac<ll>約分なしで verify (ABC301)
struct pt{
ld x,y,z;
pt():x(0),y(0),z(0){}
pt(ld xx,ld yy,ld zz):x(xx),y(yy),z(zz){}
pt operator-()const{return pt(-x,-y,-z);}
pt&operator+=(pt r){x+=r.x;y+=r.y;z+=r.z;return *this;}
pt&operator-=(pt r){x-=r.x;y-=r.y;z-=r.z;return *this;}
pt&operator*=(ld r){x*=r;y*=r;z*=r;return *this;}
pt&operator/=(ld r){x/=r;y/=r;z/=r;return *this;}
pt operator+(pt r)const{return pt(*this)+=r;}
pt operator-(pt r)const{return pt(*this)-=r;}
pt operator*(ld r)const{return pt(*this)*=r;}
pt operator/(ld r)const{return pt(*this)/=r;}
//ld length(){return sqrt(length2());}
ld length2(){return sq(x)+sq(y)+sq(z);}
int cmp(const pt&a,const pt&b)const{
int sx=sgn(a.x-b.x),sy=sgn(a.y-b.y),sz=sgn(a.z-b.z);
return sx?sx:sy?sy:sz;
}
bool operator<(pt r)const{return cmp(*this,r)<0;}
bool operator==(pt r)const{return cmp(*this,r)==0;}
};
ostream& operator<<(ostream&os, pt a){
return os<<"("<<a.x<<","<<a.y<<","<<a.z<<")";
}
istream& operator>>(istream&is, pt&a){
return is>>a.x>>a.y>>a.z;
}
ld dot(pt a,pt b){
return a.x*b.x+a.y*b.y+a.z*b.z;
}
ld norm(pt a){
return dot(a,a);
}
ld norm(pt a,pt b){
return norm(a-b);
}
bool is0(pt a){
return sgn(a.x)==0&&sgn(a.y)==0&&sgn(a.z)==0;
}
pt crs(pt a,pt b){
return pt(
a.y*b.z-a.z*b.y,
a.z*b.x-a.x*b.z,
a.x*b.y-a.y*b.x
);
}
pt crs(pt a,pt b,pt c){
return crs(b-a,c-a);
}
ld det(pt a,pt b,pt c){
return dot(crs(a,b),c);
}
//vol>0 -> a から見て b,c,d が時計まわり
ld det(pt a,pt b,pt c,pt d){
return det(b-a,c-a,d-a);
}
//TTPC2022 N
using T=tuple<pt,pt,pt>;
//面を返す; 全部三角形
//外側から見たとき,反時計まわりに列挙
//UCUP-2-20-D
//UCUP2-3-J
pt anotheraxis(pt v){
ld ax=abs(v.x),ay=abs(v.y),az=abs(v.z);
if(ax<=ay&&ax<=az)return pt(0,-v.z,v.y);
else if(ay<=az)return pt(v.z,0,-v.x);
else return pt(-v.y,v.x,0);
}
ld abs(pt v){
return sqrt(norm(v));
}
vc<T> halfpint(vc<pair<pt,ld>> hps){
//assume bounded
vc<T> res;
rep(root,si(hps)){
auto [X,off]=hps[root];
auto Y=anotheraxis(X);
Y/=abs(Y);
auto Z=crs(X,Y);
assert(sgn(abs(Z),1)==0);
vc<geo2d::ln> ls;
//for(auto [dir,thre]:hps){
rep(i,si(hps))if(i!=root){
auto [dir,thre]=hps[i];
ld x=dot(dir,X);
ld y=dot(dir,Y);
ld z=dot(dir,Z);
geo2d::pt u(y,z);
//dot(u,v)+x*off<=thre
if(u==geo2d::pt(0,0)){
if(x*off>thre)goto done;
}else{
geo2d::pt a=u*((thre-x*off)/norm(u));
auto b=a+geo2d::rot90(u);
ls.eb(a,b);
}
}
{
//dmp2(X,off);
//dmp(ls);
auto w=geo2d::halfpint(ls);
auto ch=[&](geo2d::pt q){
return X*off+Y*q.x+Z*q.y;
};
rng(i,1,si(w)-1){
res.eb(ch(w[i+1]),ch(w[i]),ch(w[0]));
}
}
done:;
}
vc<pt> vs;
for(auto [a,b,c]:res){
vs.pb(a);
vs.pb(b);
vs.pb(c);
}
mkuni(vs);
auto rectify=[&](pt v){
int i=lwb(vs,v);
assert(i<si(vs)&&vs[i]==v);
return vs[i];
};
vc<T> tmp;
for(auto [a,b,c]:res){
if(a==b||b==c||c==a)continue;
tmp.eb(rectify(a),rectify(b),rectify(c));
}
return tmp;
}
//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)));
}
ld heron(ld a,ld b,ld c){
ld s=(a+b+c)/2;
return sqrt(s*(s-a)*(s-b)*(s-c));
}
void slv(){
int n;cin>>n;
ld R;cin>>R;
//R=sqrt(R);
vc<pair<pt,ld>> hps;
{
const int V=R*2;
hps.eb(pt(+1,0,0),V);
hps.eb(pt(-1,0,0),V);
hps.eb(pt(0,+1,0),V);
hps.eb(pt(0,-1,0),V);
hps.eb(pt(0,0,+1),V);
hps.eb(pt(0,0,-1),V);
}
rep(_,n){
pt v;cin>>v;
ld len=abs(v);
pt dir=-v/len;
ld thre=sqrt(sq(len)-sq(R))/len*R;
hps.eb(dir,thre);
}
auto bound=halfpint(hps);
//dmp(bound);
vc<pt> vs;
for(auto [a,b,c]:bound){
vs.pb(a);
vs.pb(b);
vs.pb(c);
}
mkuni(vs);
unionfind uf(si(vs));
auto in=[&](pt v){
return sgn(abs(v)-R)<=0;
};
auto work=[&](pt a,pt b){
if(in(a)||in(b))return;
if(dot(a,b-a)<0&&dot(b,a-b)<0){
ld p=abs(a);
ld q=abs(b);
ld r=abs(a-b);
ld h=heron(p,q,r)*2/r;
if(sgn(h-R)<=0)return;
}
uf.unite(lwb(vs,a),lwb(vs,b));
};
for(auto [a,b,c]:bound){
work(a,b);
work(b,c);
work(c,a);
}
int ans=0;
rep(i,si(vs))if(uf.find(i)==i&&!in(vs[i])){
ans++;
}
print(ans);
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
if(dbg){
while(1)slv();
}else{
int t;cin>>t;rep(_,t)
slv();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3840kb
input:
3 4 12 13 0 0 0 15 0 0 -15 0 0 0 15 6 100 0 0 101 0 0 -101 0 101 0 0 -101 0 101 0 0 -101 0 0 20 333 328 -160 -572 -165 417 -847 -319 -45 271 359 -467 -625 -355 -451 658 -280 -424 687 -65 -224 573 475 -371 373 -246 -54 -903 595 -196 -305 622 -570 -250 386 -541 -566 647 455 -424 734 117 -405 830 -10 -...
output:
1 0 3
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 15ms
memory: 4212kb
input:
10 21 252 0 0 280 0 0 -280 0 553 0 163 528 0 311 457 0 432 345 0 514 202 0 539 -123 0 479 -276 0 376 -405 0 240 -498 0 82 -546 0 -82 -546 0 -240 -498 0 -376 -405 0 -479 -276 0 -539 -123 0 -551 41 0 -432 345 0 -311 457 0 -163 528 0 24 290 0 0 323 0 0 -323 0 638 0 180 612 0 345 537 0 482 418 0 581 265...
output:
32 44 46 48 50 20 30 23 15 2
result:
ok 10 tokens
Test #3:
score: 0
Accepted
time: 13ms
memory: 4016kb
input:
10 1 64 -152 679 262 1 61 -555 536 -388 20 41 20 62 -75 -20 -62 75 40 124 -150 -40 -124 150 60 186 -225 -60 -186 225 80 248 -300 -80 -248 300 100 310 -375 -100 -310 375 120 372 -450 -120 -372 450 140 434 -525 -140 -434 525 160 496 -600 -160 -496 600 180 558 -675 -180 -558 675 200 620 -750 -200 -620 ...
output:
1 1 1 1 1 3 1 1 4 13
result:
ok 10 tokens
Test #4:
score: 0
Accepted
time: 18ms
memory: 4020kb
input:
10 23 238 0 0 265 0 0 -265 0 522 0 154 499 0 294 431 0 408 325 0 486 191 0 520 39 0 509 -116 0 452 -261 0 355 -383 0 226 -470 0 78 -516 0 -78 -516 0 -226 -470 0 -355 -383 0 -452 -261 0 -509 -116 0 -520 39 0 -486 191 0 -408 325 0 -294 431 0 -154 499 0 24 232 0 0 258 0 0 -258 0 511 0 144 490 0 276 430...
output:
42 44 46 48 50 22 28 20 11 6
result:
ok 10 tokens
Test #5:
score: 0
Accepted
time: 70ms
memory: 4228kb
input:
10 1 78 -342 22 -830 1 22 753 206 51 28 67 -37 32 52 37 -32 -52 -74 64 104 74 -64 -104 -111 96 156 111 -96 -156 -148 128 208 148 -128 -208 -185 160 260 185 -160 -260 -222 192 312 222 -192 -312 -259 224 364 259 -224 -364 -296 256 416 296 -256 -416 -333 288 468 333 -288 -468 -370 320 520 370 -320 -520...
output:
1 1 1 1 1 1 17 1 4 14
result:
ok 10 tokens
Test #6:
score: 0
Accepted
time: 19ms
memory: 4052kb
input:
10 23 260 0 0 289 0 0 -289 0 570 0 168 545 0 321 471 0 446 355 0 531 208 0 569 43 0 556 -127 0 494 -285 0 388 -418 0 247 -514 0 85 -564 0 -85 -564 0 -247 -514 0 -388 -418 0 -494 -285 0 -556 -127 0 -569 43 0 -531 208 0 -446 355 0 -321 471 0 -168 545 0 24 205 0 0 228 0 0 -228 0 451 0 127 433 0 244 380...
output:
42 44 46 48 50 18 29 20 15 1
result:
ok 10 tokens
Test #7:
score: 0
Accepted
time: 80ms
memory: 4084kb
input:
10 1 84 -208 367 629 10 15 -53 53 -65 -106 106 -130 -159 159 -195 -212 212 -260 -265 265 -325 -318 318 -390 -371 371 -455 -424 424 -520 -477 477 -585 -530 530 -650 20 50 -61 15 72 61 -15 -72 -122 30 144 122 -30 -144 -183 45 216 183 -45 -216 -244 60 288 244 -60 -288 -305 75 360 305 -75 -360 -366 90 4...
output:
1 1 1 1 1 3 23 1 6 10
result:
ok 10 tokens
Test #8:
score: 0
Accepted
time: 23ms
memory: 4164kb
input:
10 26 190 -273 590 -183 96 -197 50 -334 465 87 134 -254 203 -39 239 -151 -192 96 -200 95 -236 50 -466 -601 406 -483 -461 -336 262 -291 -148 -317 -250 -59 -54 54 212 -117 632 116 281 168 -107 467 240 -295 527 -348 143 437 301 -86 251 132 -304 -171 -515 -335 198 83 -133 -92 -195 -274 107 325 171 231 2...
output:
4 5 8 14 6 0 4 3 4 7
result:
ok 10 tokens
Test #9:
score: 0
Accepted
time: 43ms
memory: 4208kb
input:
10 52 130 114 284 -163 651 -474 -209 -120 183 -203 -236 -268 151 -152 -124 75 -123 502 215 -403 99 350 -106 199 -154 377 664 -403 -325 -379 218 58 83 -238 484 648 -208 74 -111 323 78 201 56 53 166 40 -137 177 215 498 -426 675 -222 69 -26 161 39 166 -210 243 37 174 236 216 117 -107 -287 -127 -152 -70...
output:
4 5 7 9 5 2 19 0 1 0
result:
ok 10 tokens
Test #10:
score: 0
Accepted
time: 37ms
memory: 4004kb
input:
10 73 296 -85 518 -425 709 224 484 669 -180 601 296 376 -600 -660 -373 500 55 -783 -472 192 -835 -147 310 -153 -207 -494 -188 -102 -686 480 -246 -626 -457 -564 105 63 699 -460 527 427 -594 23 -510 -251 572 -130 765 203 -47 250 385 -138 -211 785 417 192 -767 -155 -75 111 -382 655 -398 -557 16 -74 -86...
output:
4 8 4 6 1 4 4 0 5 0
result:
ok 10 tokens
Test #11:
score: 0
Accepted
time: 31ms
memory: 3952kb
input:
10 125 133 579 746 180 135 752 -291 42 -651 -652 94 -313 801 207 154 -772 118 279 923 -385 -407 49 355 -35 -723 292 52 352 -865 -230 99 -698 -43 143 -476 -838 117 -10 -633 -452 -97 -475 301 667 479 467 356 188 777 107 94 627 423 -670 -103 578 -48 -300 320 715 -483 433 -269 -771 223 -758 543 19 -87 1...
output:
9 5 8 1 7 7 5 10 9 0
result:
ok 10 tokens
Test #12:
score: 0
Accepted
time: 699ms
memory: 4072kb
input:
10 500 104 61 296 49 -313 -843 -229 348 516 46 84 -102 196 -272 -94 -274 424 437 -115 -77 -606 194 -194 -138 -102 412 284 102 -580 123 -393 183 -618 102 234 867 -159 242 -237 883 95 -11 -298 -62 203 196 -454 -851 -136 393 -484 618 -52 94 61 -310 -105 -42 55 -16 141 -14 156 -8 -151 18 93 -176 -550 17...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 tokens
Test #13:
score: 0
Accepted
time: 698ms
memory: 4076kb
input:
10 500 114 93 -268 -242 -148 -268 -291 -199 69 110 -165 -178 77 76 34 -453 -246 -443 291 -144 337 636 -402 35 -718 22 -79 97 -845 259 -159 -157 -463 328 304 564 -164 -90 -438 -112 -223 -38 29 -26 322 72 -628 114 -754 307 -265 -229 -772 -181 -197 -212 377 132 700 2 -16 -719 31 -151 372 41 564 142 25 ...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 tokens
Test #14:
score: 0
Accepted
time: 3ms
memory: 3952kb
input:
10 15 10 431 -214 -126 564 55 16 -5 192 -599 566 753 76 406 -573 549 47 589 -568 -505 -389 -486 -505 243 260 -650 -220 -411 -890 302 -327 -176 737 -422 103 502 -121 -223 -312 -648 291 -523 -45 -184 90 -636 20 19 675 149 -602 713 -539 -253 283 618 442 -187 662 -680 177 -844 60 163 148 264 158 505 -77...
output:
1 1 1 1 1 1 1 1 1 1
result:
ok 10 tokens
Test #15:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
10 24 17 521 286 -776 -115 -70 193 -211 -388 -38 255 -586 -309 -443 809 49 637 -278 -195 926 -206 183 598 642 -479 -825 55 404 208 -106 240 -745 -344 -547 194 225 -442 -61 533 -149 -648 608 386 -640 14 517 412 -309 184 537 42 685 731 353 238 300 -14 -227 -810 153 -486 -510 -28 -828 -454 424 293 497 ...
output:
1 1 1 1 1 1 1 1 1 1
result:
ok 10 tokens
Test #16:
score: 0
Accepted
time: 1ms
memory: 4056kb
input:
3 4 100 111 0 0 101 0 0 1000 0 0 628 0 0 3 314 0 431 0 0 999 0 0 341 0 7 7 0 0 77 0 0 777 0 0 70 0 0 770 0 0 707 0 0 700 0 0 -777
output:
1 1 1
result:
ok 3 tokens
Test #17:
score: 0
Accepted
time: 1ms
memory: 4032kb
input:
3 16 64 32 64 0 2 256 0 128 8 0 512 0 0 4 -128 0 256 -8 0 128 -2 0 0 -256 0 -4 -128 0 -32 -64 0 -512 -1 0 -128 0 0 -512 1 0 -8 512 0 -128 4 0 0 128 0 6 123 0 666 0 0 -666 0 0 333 576 0 333 -576 0 -333 576 0 -333 -576 4 999 707 0 707 707 0 -707 -707 0 707 -707 0 -707
output:
1 1 2
result:
ok 3 tokens
Test #18:
score: 0
Accepted
time: 266ms
memory: 4240kb
input:
10 300 121 -973 -95 -199 -561 -803 189 652 -552 -517 421 315 848 -208 -741 635 357 776 516 -423 -901 73 -894 52 440 -473 -799 365 605 503 614 622 743 238 84 -189 976 759 -118 638 -69 891 444 -497 -52 864 293 604 -739 -409 900 134 211 959 -180 434 -566 698 621 -34 780 -997 -8 -48 568 -12 -820 -678 -1...
output:
317 317 317 317 317 317 317 317 317 317
result:
ok 10 tokens
Test #19:
score: 0
Accepted
time: 735ms
memory: 4952kb
input:
10 500 95 -99 38 -992 -182 -153 -969 -693 -632 342 -828 556 39 -146 925 344 600 -779 -174 -589 -796 126 86 797 -594 -626 -260 -732 843 451 -286 366 -928 -31 -822 267 498 -747 485 450 -334 82 -937 -214 177 -959 681 -265 680 9 -953 -297 488 -834 -250 -818 -542 -183 -99 -613 781 -818 -481 -310 -964 -45...
output:
457 457 457 457 457 457 457 457 457 457
result:
ok 10 tokens
Test #20:
score: 0
Accepted
time: 616ms
memory: 4800kb
input:
10 411 96 970 0 -235 51 54 995 -125 -907 -397 835 190 512 -463 648 -601 71 949 300 326 743 -581 -699 -646 -300 925 118 -356 907 -378 175 -442 561 697 -743 632 211 842 -516 -146 -286 -227 929 -197 895 395 -258 -910 -318 908 381 -163 -643 382 -661 557 635 532 -961 -251 -102 -565 787 -241 714 490 -497 ...
output:
283 410 89 12 6 2 407 297 460 0
result:
ok 10 tokens
Test #21:
score: 0
Accepted
time: 605ms
memory: 4880kb
input:
10 429 91 -143 867 -473 -835 545 -54 -829 -325 -452 930 100 -348 -282 -274 -917 -494 456 -738 -932 154 -322 -996 32 -47 -428 -893 124 256 698 -666 -227 -131 963 919 -230 313 641 747 -165 -913 -383 -125 476 161 -863 -408 -665 -623 -912 -286 289 -405 479 776 -974 6 -218 607 553 568 -371 770 515 -139 -...
output:
199 377 358 486 40 133 377 327 3 340
result:
ok 10 tokens
Extra Test:
score: 0
Extra Test Passed