QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87426 | #3184. Around the Track | ExplodingKonjac | WA | 2ms | 3628kb | C++17 | 6.8kb | 2023-03-12 21:05:06 | 2023-03-12 21:05:09 |
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<=n1;j++) if(inside(p1[j],{A,B,C})) np.push_back(p1[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: 2ms
memory: 3628kb
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: 0ms
memory: 3592kb
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: -100
Wrong Answer
time: 1ms
memory: 3592kb
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.00000000
result:
wrong answer 1st numbers differ - expected: '16.4721360', found: '16.0000000', error = '0.0286627'