QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87427 | #3184. Around the Track | ExplodingKonjac | WA | 2ms | 3724kb | C++17 | 6.8kb | 2023-03-12 21:06:58 | 2023-03-12 21:07:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<22;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
};
class FastOutput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x,target);
#endif
}
template<typename T>
inline void __write(T x)
{
static char stk[64],*top;top=stk;
if(x<0) return __putc('-'),__write(-x);
do *(top++)=x%10,x/=10; while(x);
for(;top!=stk;__putc(*(--top)+'0'));
}
public:
FastOutput(FILE *f=stdout): FastIOBase(f){}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target=f; }
#endif
template<typename ...T>
inline void writesp(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
template<typename ...T>
inline void writeln(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
inline FastOutput &operator <<(char x)
{ return __putc(x),*this; }
inline FastOutput &operator <<(const char *s)
{ for(;*s;__putc(*(s++)));return *this; }
inline FastOutput &operator <<(const string &s)
{ return (*this)<<s.c_str(); }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator <<(const T &x)
{ return __write(x),*this; }
}qout;
class FastInput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc()
{
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f=stdin): FastIOBase(f){}
inline void setTarget(FILE *f) { target=f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x)
{ initializer_list<int>{(this->operator>>(x),0)...}; }
inline FastInput &operator >>(char &x)
{ while(isspace(x=__getc()));return *this; }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator >>(T &x)
{
static char ch,sym;x=sym=0;
while(isspace(ch=__getc()));
if(ch=='-') sym=1,ch=__getc();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=__getc());
return sym?x=-x:x,*this;
}
inline FastInput &operator >>(char *s)
{
while(isspace(*s=__getc()));
for(;!isspace(*s) && *s && ~*s;*(++s)=__getc());
return *s='\0',*this;
}
inline FastInput &operator >>(string &s)
{
char str_buf[(1<<8)+1],*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=__getc()));
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=__getc()) && *p && ~*p;p++);
*p='\0',s.append(str_buf);
if(p!=buf_end) break;
}
return *this;
}
}qin;
} // namespace FastIO
using namespace FastIO;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#else
#define FILEIO(file)
#endif
template<typename T>
struct Vector
{
T x,y;
bool ban;
Vector(): x(0),y(0){}
Vector(T _x,T _y,bool _ban=false): x(_x),y(_y),ban(_ban){}
inline Vector &operator +=(const Vector &rhs)
{ return x+=rhs.x,y+=rhs.y,*this; }
inline Vector &operator -=(const Vector &rhs)
{ return x-=rhs.x,y-=rhs.y,*this; }
inline Vector &operator *=(T scale)
{ return x*=scale,y*=scale,*this; }
inline Vector operator +(const Vector &rhs)const
{ return Vector(*this)+=rhs; }
inline Vector operator -(const Vector &rhs)const
{ return Vector(*this)-=rhs; }
inline T operator *(const Vector &rhs)const
{ return x*rhs.y-y*rhs.x; }
inline T operator %(const Vector &rhs)const
{ return x*rhs.x-y*rhs.y; }
friend inline Vector operator *(T scale,const Vector &u)
{ return Vector(u)*=scale; }
friend inline Vector operator *(const Vector &u,T scale)
{ return Vector(u)*=scale; }
inline bool operator <(const Vector &rhs)const
{ return x!=rhs.x?x<rhs.x:y<rhs.y; }
inline bool operator ==(const Vector &rhs)const
{ return x==rhs.x && y==rhs.y; }
inline bool operator !=(const Vector &rhs)const
{ return x!=rhs.x || y!=rhs.y; }
friend inline auto abs(const Vector &u)
{ return hypot(u.x,u.y); }
friend inline auto abs2(const Vector &u)
{ return u.x*u.x+u.y*u.y; }
friend inline auto arg(const Vector &u)
{ return atan2(u.y,u.x); }
friend inline Vector rotate(const Vector &u,T t)
{ return Vector(u.x*cos(t)-u.y*sin(t),u.x*sin(t)+u.y*cos(t),u.id); }
};
using Vec=Vector<LL>;
int n1,n2;
Vec p1[55],p2[55]; // 1: inner, 2: outer
inline bool inside(const Vec &p,const array<Vec,3> &T)
{
LL val1=(p-T[0])*(T[1]-T[0]),
val2=(p-T[1])*(T[2]-T[1]),
val3=(p-T[2])*(T[0]-T[2]);
bool res=false;
res|=(val1<0 && val2<0 && val3<0);
res|=(val1>0 && val2>0 && val3>0);
return res;
}
vector<Vec> convex(vector<Vec> p)
{
if(p.size()<=1) return p;
int N=p.size(),M=0;
Vec O=p[0];
sort(p.begin()+1,p.end(),[&O](const Vec &u,const Vec &v)
{
LL x=(u-O)*(v-O);
if(x) return x>0;
return abs2(u-O)<abs2(v-O);
});
for(int i=1;i<N;i++)
{
while(M && (p[i]-p[M-1])*(p[M]-p[M-1])>=0) M--;
p[++M]=p[i];
}
return p.resize(M+1),p;
}
double solve()
{
vector<Vec> p(p1+1,p1+n1+1);
while(true)
{
int sz=p.size();
auto pre=[sz](int i){ return (i?i:sz)-1; };
bool nothing=true;
for(int i=0;i<sz;i++)
{
int pi=pre(i),ppi=pre(pi);
Vec A=p[i],B=p[pi],C=p[ppi];
if(B.ban || (A-C)*(B-C)<0) continue;
vector<Vec> np{C};
for(int j=1;j<=n2;j++) if(inside(p2[j],{A,B,C})) np.push_back(p2[j]);
for(int j=0;j<sz;j++) if(inside(p[j],{A,B,C})) np.push_back(p[j]);
np.push_back(A);
np=convex(np),reverse(np.begin()+2,np.end());
for(auto &j: np) j.ban=true;
p.erase(p.begin()+pi);
p.insert(p.begin()+i-(pi<i),np.begin()+2,np.end());
nothing=false;break;
}
if(nothing) break;
}
double res=abs(p[0]-p.back());
for(int i=1;i<p.size();i++) res+=abs(p[i-1]-p[i]);
return res;
}
int main()
{
qin>>n1;
for(int i=1;i<=n1;i++) qin>>p1[i].x>>p1[i].y;
qin>>n2;
for(int i=1;i<=n2;i++) qin>>p2[i].x>>p2[i].y;
double ans=solve();
cout<<setprecision(8)<<fixed<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
3 1 1 2 1 1 2 3 0 0 4 0 0 4
output:
3.41421356
result:
ok found '3.4142136', expected '3.4142136', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
5 1 1 5 1 5 5 3 3 1 5 4 0 0 6 0 6 6 0 6
output:
16.00000000
result:
ok found '16.0000000', expected '16.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
5 1 1 5 1 5 5 3 3 1 5 5 0 0 6 0 6 6 3 4 0 6
output:
16.47213595
result:
ok found '16.4721359', expected '16.4721360', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
5 2 2 6 2 6 6 4 4 2 6 4 0 0 8 0 8 8 0 8
output:
16.00000000
result:
ok found '16.0000000', expected '16.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
5 2 2 6 2 6 6 4 4 2 6 5 0 0 8 0 8 8 4 5 0 8
output:
16.47213595
result:
ok found '16.4721359', expected '16.4721360', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
12 1 1 1 4 -1 4 -1 1 -4 1 -4 -1 -1 -1 -1 -4 1 -4 1 -1 4 -1 4 1 12 2 2 2 5 -2 5 -2 2 -5 2 -5 -2 -2 -2 -2 -5 2 -5 2 -2 5 -2 5 2
output:
25.88854382
result:
ok found '25.8885438', expected '25.8885438', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 6 10 3 9 6 8 5 7 6 6 3 5 6 4 4 3 8 0 8
output:
43.68323851
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 8 10 3 9 8 8 5 7 8 6 3 5 8 4 4 3 8 0 8
output:
43.68323851
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 7 10 3 9 7 8 5 7 7 6 3 5 7 4 4 3 8 0 8
output:
43.68323851
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
12 1 1 10 1 10 6 9 6 9 2 6 2 6 4 5 4 5 2 2 2 2 6 1 6 12 0 0 11 0 11 7 8 7 8 3 7 3 7 5 4 5 4 3 3 3 3 7 0 7
output:
33.15298245
result:
ok found '33.1529825', expected '33.1529824', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3724kb
input:
7 1 1 5 1 5 19 4 2 3 18 2 2 1 19 9 0 0 6 0 6 20 5 20 4 3 3 19 2 3 1 20 0 20
output:
102.12903184
result:
ok found '102.1290318', expected '102.1290318', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3528kb
input:
12 1 1 12 1 12 5 11 5 11 2 8 2 8 6 7 6 7 2 2 2 2 5 1 5 16 0 0 13 0 13 9 4 9 4 4 5 4 5 8 10 8 10 3 9 3 9 7 6 7 6 3 3 3 3 6 0 6
output:
36.79669128
result:
ok found '36.7966913', expected '36.7966913', error '0.0000000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
12 1 1 12 1 12 5 11 5 11 2 8 2 8 6 7 6 7 2 2 2 2 5 1 5 12 0 0 13 0 13 9 4 9 4 4 5 4 5 8 6 8 6 3 3 3 3 6 0 6
output:
33.52145126
result:
ok found '33.5214513', expected '33.5214513', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
8 1 3 4 2 4 1 5 4 6 4 3 5 3 6 2 3 4 0 0 7 0 7 7 0 7
output:
14.42220510
result:
ok found '14.4222051', expected '14.4222051', error '0.0000000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
8 1 2 2 1 4 3 4 5 5 5 4 6 2 4 2 2 4 2 0 6 4 4 7 0 3
output:
12.95741733
result:
ok found '12.9574173', expected '12.9574173', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
8 2 2 4 2 6 4 5 5 5 4 3 4 1 2 2 1 4 3 0 7 4 4 6 0 2
output:
12.95741733
result:
ok found '12.9574173', expected '12.9574173', error '0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
12 1 3 4 2 9 2 9 1 10 4 10 9 11 9 8 10 3 10 3 11 2 8 2 3 4 0 3 9 0 12 9 3 12
output:
33.04518870
result:
ok found '33.0451887', expected '33.0451887', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
44 21 -7 21 5 20 5 20 -6 17 -6 17 4 16 4 16 -5 13 -5 13 3 12 3 12 -4 9 -4 9 2 8 2 8 -3 5 -3 5 1 4 1 4 -2 1 -2 1 0 -1 0 -1 -2 -4 -2 -4 1 -5 1 -5 -3 -8 -3 -8 2 -9 2 -9 -4 -12 -4 -12 3 -13 3 -13 -5 -16 -5 -16 4 -17 4 -17 -6 -20 -6 -20 5 -21 5 -21 -7 44 22 -8 22 6 19 6 19 -5 18 -5 18 5 15 5 15 -4 14 -4 ...
output:
200.71206638
result:
ok found '200.7120664', expected '200.7120664', error '0.0000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
47 23 -13 22 11 21 -12 20 10 19 -11 18 9 17 -10 16 8 15 -9 14 7 13 -8 12 6 11 -7 10 5 9 -6 8 4 7 -5 6 3 5 -4 4 2 3 -3 2 1 1 -2 0 0 -1 -2 -2 1 -3 -3 -4 2 -5 -4 -6 3 -7 -5 -8 4 -9 -6 -10 5 -11 -7 -12 6 -13 -8 -14 7 -15 -9 -16 8 -17 -10 -18 9 -19 -11 -20 10 -21 -12 -22 11 -23 -13 47 24 -14 22 12 21 -11...
output:
603.51467796
result:
ok found '603.5146780', expected '603.5146780', error '0.0000000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
8 -10 0 -10 -10 0 -10 10 -10 10 0 10 10 0 10 -10 10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.00000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
8 0 10 -10 10 -10 0 -10 -10 0 -10 10 -10 10 0 10 10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.00000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
8 10 0 10 10 0 10 -10 10 -10 0 -10 -10 0 -10 10 -10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.00000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
8 0 -10 10 -10 10 0 10 10 0 10 -10 10 -10 0 -10 -10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.00000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
4 -1000 -1000 0 0 1000 -1000 0 2000 50 1500 -1500 0 2500 -1500 -1500 -460 -730 -440 -720 -420 -710 -400 -700 -380 -690 -360 -680 -340 -670 -320 -660 -300 -650 -280 -640 -260 -630 -240 -620 -220 -610 -200 -600 -180 -590 -160 -580 -140 -570 -120 -560 -100 -550 -80 -540 -60 -530 -40 -520 -20 -510 0 -50...
output:
8560.62329784
result:
ok found '8560.6232978', expected '8560.6232978', error '0.0000000'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
4 -1 -1 1 -1 1 1 -1 1 16 1 3 -1 3 -1 2 -2 1 -3 1 -3 -1 -2 -1 -1 -2 -1 -3 1 -3 1 -2 2 -1 3 -1 3 1 2 1 1 2
output:
8.00000000
result:
ok found '8.0000000', expected '8.0000000', error '0.0000000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
8 0 -1 3 -3 1 0 3 3 0 1 -3 3 -1 0 -3 -3 20 0 -2 7 -9 5 -6 6 -5 9 -7 2 0 9 7 6 5 5 6 7 9 0 2 -7 9 -5 6 -6 5 -9 7 -2 0 -9 -7 -6 -5 -5 -6 -7 -9
output:
25.29822128
result:
ok found '25.2982213', expected '25.2982213', error '0.0000000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
5 5 5 3 3 1 5 1 1 5 1 5 0 0 6 0 6 6 3 4 0 6
output:
16.47213595
result:
ok found '16.4721359', expected '16.4721360', error '0.0000000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
12 45 45 135 45 135 108 243 108 162 45 315 45 270 225 189 225 234 117 135 117 162 225 45 108 16 0 0 138 0 138 93 143 98 148 72 211 99 155 44 342 -45 360 270 180 270 192 125 175 122 169 125 161 270 0 180 0 90
output:
1158.35315175
result:
ok found '1158.3531518', expected '1158.3531517', error '0.0000000'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
4 -360 180 -297 270 -360 315 -405 225 6 -45 45 -270 270 -90 288 -90 450 -450 495 -540 135
output:
351.54259724
result:
ok found '351.5425972', expected '351.5425972', error '0.0000000'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
49 0 -1 460 -1 460 0 450 999 440 0 430 999 420 0 410 999 400 0 390 999 380 0 370 999 360 0 350 999 340 0 330 999 320 0 310 999 300 0 290 999 280 0 270 999 260 0 250 999 240 0 230 999 220 0 210 999 200 0 190 999 180 0 170 999 160 0 150 999 140 0 130 999 120 0 110 999 100 0 90 999 80 0 70 999 60 0 50 ...
output:
46374.30445108
result:
ok found '46374.3044511', expected '46374.3044511', error '0.0000000'
Test #31:
score: -100
Wrong Answer
time: 2ms
memory: 3596kb
input:
50 -2255 1931 -2830 -3187 3406 -4113 -1883 -1838 2327 -1793 425 -1197 2782 -1197 -569 -601 -6 -1566 -1556 -1182 -793 124 3186 -187 481 523 1688 652 -1844 580 2726 1263 -1544 1419 2655 1961 -389 1916 2623 2899 -3785 4421 -4440 3211 -2902 3483 -4580 -3486 -2403 3382 -537 3211 425 2728 -1005 2345 -1696...
output:
72041.18885172
result:
wrong answer 1st numbers differ - expected: '67111.7337452', found: '72041.1888517', error = '0.0734515'