QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750361 | #6118. Eartheart | Crysfly | WA | 1ms | 6060kb | C++14 | 8.7kb | 2024-11-15 14:18:53 | 2024-11-15 14:18:53 |
Judging History
answer
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
typedef double db;
const db eps=1e-10,pi=3.14159265358979323846;
int sgn(db x){return x<-eps?-1:x>eps;}
int cmp(db a,db b){return sgn(a-b);}
struct P{
db x,y;
P(db x=0,db y=0):x(x),y(y){}
P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
P&operator *=(db o){return x*=o,y*=o,*this;}
P&operator /=(db o){return x/=o,y/=o,*this;}
friend P operator +(P a,P b){return a+=b;}
friend P operator -(P a,P b){return a-=b;}
friend P operator *(P a,db b){return a*=b;}
friend P operator /(P a,db b){return a/=b;}
friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
friend bool operator !=(P a,P b){return !(a==b);}
friend db operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
friend db operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
P rot(db o){
db s=sin(o),c=cos(o);
return P(x*c-y*s,x*s+y*c);
}
P rot90(){return P(-y,x);}
db ang(){return atan2(y,x);}
db len(){return sqrt(x*x+y*y);}
db len2(){return x*x+y*y;}
int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
P unit(){return ((*this))/len();}
void read(){cin>>x>>y;}
void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
if(a.half()!=b.half())return a.half()<b.half();
return sgn(a*b)>0;
}
db dis(P a,P b){return (a-b).len();}
db cross(P a,P b,P c){
// (a->b)*(a->c)
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
return sgn(cross(a,b,c));
}
bool in_tri(P a,P b,P c,P p){
if(cmp3(a,b,c)<0) swap(b,c);
return cmp3(a,b,p)>=0 && cmp3(b,c,p)>=0 && cmp3(c,a,p)>=0;
}
db area_tri(P a,P b,P c){
return fabs(cross(a,b,c))/2;
}
bool paral(P p1,P p2,P q1,P q2){
// is parallel
return sgn((p2-p1)*(q2-q1))==0;
}
P interl(P p1,P p2,P q1,P q2){
// intersect point
db s1=cross(q1,q2,p1),s2=-cross(q1,q2,p2);
return (p1*s2+p2*s1)/(s1+s2);
}
bool inter(db l1,db r1,db l2,db r2){
if(l1>r1)swap(l1,r1); if(l2>r2)swap(l2,r2);
return !(cmp(r1,l2)==-1||cmp(r2,l1)==-1);
}
bool ismid(db a,db m,db b){
return sgn(a-m)==0||sgn(b-m)==0||((a<m)!=(b<m));
}
bool ismid(P a,P m,P b){
return ismid(a.x,m.x,b.x)&&ismid(a.y,m.y,b.y);
}
bool isseg(P p1,P p2,P q1,P q2){
return inter(p1.x,p2.x,q1.x,q2.x) && inter(p1.y,p2.y,q1.y,q2.y) &&
cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<=0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<=0;
}
bool isseg_strict(P p1,P p2,P q1,P q2){
return cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<0;
}
struct L{
P a,b;
L(P aa=P(0,0),P bb=P(0,0)){a=aa,b=bb;}
bool in(P p){return sgn((b-a)*(p-a))>0;}
int in_sgn(P p){return sgn((b-a)*(p-a));}
P dir(){return b-a;}
bool onl(P p){
return cmp3(a,b,p)==0;
}
bool onseg(P p){
return onl(p)&&ismid(a,p,b);
}
bool onseg_strict(P p){
return onl(p)&&sgn((p-a)%(a-b))*sgn((p-b)%(a-b))<0;
}
void out(){cout<<"("<<a.x<<","<<a.y<<")---("<<b.x<<","<<b.y<<")\n";}
};
bool isseg(L a,L b){
return isseg(a.a,a.b,b.a,b.b);
}
bool paral(L a,L b){
// is parallel
return paral(a.a,a.b,b.a,b.b);
}
P operator &(L a,L b){
return interl(a.a,a.b,b.a,b.b);
}
bool samedir(L a,L b){
return paral(a,b) && sgn(a.dir()%b.dir())==1;
}
bool operator <(L a,L b){
if(samedir(a,b)) return b.in(a.a);
return cmp_dir(a.dir(),b.dir());
}
P proj(L a,P b){
P d=a.dir();
return a.a+d*((d%(b-a.a))/d.len2());
}
P reflect(L a,P b){
return proj(a,b)*2-b;
}
db dis(L a,P b){
db s=abs((b-a.a)*(b-a.b));
return s/dis(a.a,a.b);
}
db dis_seg(L a,P b){
if(a.a==a.b) return dis(a.a,b);
P h=proj(a,b);
if(ismid(a.a,h,a.b)) return dis(h,b);
return min(dis(a.a,b),dis(a.b,b));
}
db dis_ss(L a,L b){
if(isseg(a,b)) return 0;
return min(min(dis_seg(a,b.a),dis_seg(a,b.b)),min(dis_seg(b,a.a),dis_seg(b,a.b)));
}
db rad(P a,P b){
return atan2l(a*b,a%b);
}
// polygon
db area(vector<P>a){
db res=0;
For(i,0,(int)a.size()-1)res+=a[i]*a[(i+1)%a.size()];
return res/2;
}
int contain(vector<P>a,P p){
int n=a.size(),res=0;
For(i,0,n-1){
P u=a[i],v=a[(i+1)%n];
if(L(u,v).onseg(p))return 1;
if(cmp(u.y,v.y)<=0)swap(u,v);
if(cmp(p.y,u.y)>0 || cmp(p.y,v.y)<=0)continue;
res^=cmp3(p,u,v)>0;
}
return res*2;
}
vector<P>cut(vector<P>&a,P q1,P q2){
vector<P>b; int n=a.size();
For(i,0,n-1){
P p1=a[i],p2=a[(i+1)%n];
int d1=cmp3(q1,q2,p1),d2=cmp3(q1,q2,p2);
if(d1>=0)b.pb(p1);
if(d1*d2<0)b.pb(interl(p1,p2,q1,q2));
}
return b;
}
vector<P>cut(vector<P>&a,L l){
return cut(a,l.a,l.b);
}
vector<P>convex(vector<P>a){
int n=a.size(),m=0; if(n<=1)return a;
sort(a.begin(),a.end());
vector<P>st(n*2); int tp=0;
For(i,0,n-1){
while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
st[tp++]=a[i];
}
int t=tp;
Rep(i,n-2,0){
while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
st[tp++]=a[i];
}
st.resize(tp-1);
return st;
}
// <=0 to <0: non-strict (need to unique points)
bool check(L a,L b,L c){
return c.in(a&b);
}
int checksgn(L a,L b,L c){
return c.in_sgn(a&b);
}
vector<P>hpis(vector<L>&l){
sort(l.begin(),l.end());
deque<L>q;
For(i,0,(int)l.size()-1){
if(i&&samedir(l[i],l[i-1]))continue;
while(q.size()>1 && !check(q[q.size()-2],q[q.size()-1],l[i]))q.pop_back();
while(q.size()>1 && !check(q[1],q[0],l[i]))q.pop_front();
q.pb(l[i]);
}
while(q.size()>2 && !check(q[q.size()-2],q[q.size()-1],q[0]))q.pop_back();
while(q.size()>2 && !check(q[1],q[0],q[q.size()-1]))q.pop_front();
vector<P>res;
For(i,0,(int)q.size()-1) res.pb(q[i]&q[(i+1)%q.size()]);
return res;
}
mt19937_64 rnd(64);
vector<L>cut(vector<L>&a,L l){
vector<L>b; int n=a.size();
For(i,0,n-1){
L a1=a[i],a2=a[(i+1)%n],a3=a[(i+2)%n];
int d1=checksgn(a1,a2,l),d2=checksgn(a2,a3,l);
if(d1>0 || d2>0 || (d1==0&&d2==0)) b.pb(a2);
if(d1>=0 && d2<0) b.pb(l);
}
return b;
}
// circles
struct cir{
P o; db r;
cir(P oo=P(0,0),db rr=0){o=oo,r=rr;}
bool in(P x){return sgn(dis(x,o)-r)<=0;}
bool in_strict(P x){return sgn(dis(x,o)-r)<0;}
};
int type(cir a,cir b){
db d=dis(a.o,b.o);
if(cmp(d,a.r+b.r)==1)return 4;
if(cmp(d,a.r+b.r)==0)return 3;
if(cmp(d,fabs(a.r-b.r))==1)return 2;
if(cmp(d,fabs(a.r-b.r))==0)return 1;
return 0;
}
// cir&line
vector<P> operator &(cir a,L b){
if(cmp(abs(((a.o-b.a)*(b.b-b.a))/dis(b.a,b.b)),a.r)>=0) return {};
db x=(b.a-a.o)%(b.b-b.a);
db y=(b.b-b.a).len2();
db d=x*x-y*((b.a-a.o).len2()-a.r*a.r);
d=max(d,(db)0.0);
P m=b.a-(b.b-b.a)*(x/y);
P dr=(b.b-b.a)*(sqrt(d)/y);
return {m-dr,m+dr}; //along dir: p1->p2
}
#define maxn 300005
#define inf 0x3f3f3f3f
int n;
db R;
vector<P>p;
vector<pair<db,db>>vec;
db t[maxn]; int len;
void sausage(P a,P b){
if(cmp(a.y,R)>=0 && cmp(b.y,R)>=0) return ;
if(cmp(a.y,-R)<=0 && cmp(b.y,-R)<=0) return ;
P t=(b-a).rot90();
t/=t.len(),t*=R;
L my=L(P(min(a.x,b.x)-R*2,0),P(max(a.x,b.x)+R*2,0));
db ql=1e100,qr=-ql;
for(auto l1:{L(a-t,b-t),L(a+t,b+t)})
if(isseg(my,l1)) {
P ps=(my&l1);
//cout<<"PS "<<ps.x<<"\n";
ql=min(ql,ps.x),qr=max(qr,ps.x);
}
// cout<<"R: "<<R<<"\n";
for(auto cr:{cir(a,R),cir(b,R)}){
vector<P>tmp=(cr&my);
if(tmp.size()){
for(auto ps:tmp){
// ps.out();
ql=min(ql,ps.x),qr=max(qr,ps.x);
}
}
}
if(ql>qr) return;
vec.pb(mkp(ql,qr));
//cerr<<"l,r "<<ql<<" "<<qr<<"\n";
::t[++len]=ql,::t[++len]=qr;
}
int ban[maxn],c[maxn];
signed main()
{
cin>>n>>R;
p.resize(n);
For(i,0,n-1)cin>>p[i].x>>p[i].y;
For(i,0,n-1)sausage(p[i],p[(i+1)%n]);
t[++len]=-1e18,t[++len]=1e18;
sort(t+1,t+len+1); len=unique(t+1,t+len+1)-t-1;
for(auto [l,r]:vec){
int ql=lower_bound(t+1,t+len+1,l)-t;
int qr=lower_bound(t+1,t+len+1,r)-t;
c[ql]^=1;
ban[ql]++,ban[qr]--;
}
db res=0;
For(i,1,len){
ban[i]+=ban[i-1];
c[i]^=c[i-1];
//cout<<"i: "<<i<<" "<<ban[i]<<" "<<c[i]<<"\n";
//cout<<"l,r "<<t[i]<<" "<<t[i+1]<<"\n";
if(i<len && !ban[i] && c[i])res+=t[i+1]-t[i];//cout<<"add\n";
}
printf("%.14lf\n",res);
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6060kb
input:
4 5 -5 -5 5 -5 5 5 -5 5
output:
0.00000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
4 5 -10 -10 10 -10 10 10 -10 10
output:
10.00000000000000
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
9 10 -100 -80 -90 130 -30 150 0 160 100 130 120 90 110 -60 80 -100 0 -120
output:
190.15694715649968
result:
ok found '190.15695', expected '190.15695', error '0.00000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3912kb
input:
457 414687 -996315 -725321 -986403 -603614 -984900 -99226 -943685 -319681 -985352 -704158 -984699 -905259 -969935 -927143 -465900 -963727 -310171 -992145 -453426 -949729 -643489 -909695 -709791 -884030 -787622 -849046 -526296 -903166 -408863 -906869 -263787 -933392 -473870 -789072 -593393 -759966 -6...
output:
999999999998590464.00000000000000
result:
wrong answer 1st numbers differ - expected: '0.00000', found: '999999999998590464.00000', error = '999999999998590464.00000'