QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357016 | #5104. Guardians of the Gallery | TadijaSebez | TL | 538ms | 4128kb | C++14 | 21.3kb | 2024-03-18 17:31:03 | 2024-03-18 17:31:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define pb push_back
#define ldb double
//-----------------Big int-----------------------//
// Fast Fourier transform
// https://cp-algorithms.com/algebra/fft.html
// https://drive.google.com/file/d/1B9BIfATnI_qL6rYiE5hY9bh20SMVmHZ7/view
using cpx = complex<double>;
const double PI = acos(-1);
vector<cpx> roots = {{0, 0}, {1, 0}};
void ensure_capacity(int min_capacity) {
for (int len = roots.size(); len < min_capacity; len *= 2) {
for (int i = len >> 1; i < len; i++) {
roots.emplace_back(roots[i]);
double angle = 2 * PI * (2 * i + 1 - len) / (len * 2);
roots.emplace_back(cos(angle), sin(angle));
}
}
}
void fft(vector<cpx> &z, bool inverse) {
int n = z.size();
assert((n & (n - 1)) == 0);
ensure_capacity(n);
for (unsigned i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j >= bit; bit >>= 1)
j -= bit;
j += bit;
if (i < j)
swap(z[i], z[j]);
}
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len * 2) {
for (int j = 0; j < len; j++) {
cpx root = inverse ? conj(roots[j + len]) : roots[j + len];
cpx u = z[i + j];
cpx v = z[i + j + len] * root;
z[i + j] = u + v;
z[i + j + len] = u - v;
}
}
}
if (inverse)
for (int i = 0; i < n; i++)
z[i] /= n;
}
vector<int> multiply_bigint(const vector<int> &a, const vector<int> &b, int base) {
int need = a.size() + b.size();
int n = 1;
while (n < need)
n <<= 1;
vector<cpx> p(n);
for (size_t i = 0; i < n; i++) {
p[i] = cpx(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
}
fft(p, false);
// a[w[k]] = (p[w[k]] + conj(p[w[n-k]])) / 2
// b[w[k]] = (p[w[k]] - conj(p[w[n-k]])) / (2*i)
vector<cpx> ab(n);
cpx r(0, -0.25);
for (int i = 0; i < n; i++) {
int j = (n - i) & (n - 1);
ab[i] = (p[i] * p[i] - conj(p[j] * p[j])) * r;
}
fft(ab, true);
vector<int> result(need);
long long carry = 0;
for (int i = 0; i < need; i++) {
long long d = (long long)(ab[i].real() + 0.5) + carry;
carry = d / base;
result[i] = d % base;
}
return result;
}
vector<int> multiply_mod(const vector<int> &a, const vector<int> &b, int m) {
int need = a.size() + b.size() - 1;
int n = 1;
while (n < need)
n <<= 1;
vector<cpx> A(n);
for (size_t i = 0; i < a.size(); i++) {
int x = (a[i] % m + m) % m;
A[i] = cpx(x & ((1 << 15) - 1), x >> 15);
}
fft(A, false);
vector<cpx> B(n);
for (size_t i = 0; i < b.size(); i++) {
int x = (b[i] % m + m) % m;
B[i] = cpx(x & ((1 << 15) - 1), x >> 15);
}
fft(B, false);
vector<cpx> fa(n);
vector<cpx> fb(n);
for (int i = 0, j = 0; i < n; i++, j = n - i) {
cpx a1 = (A[i] + conj(A[j])) * cpx(0.5, 0);
cpx a2 = (A[i] - conj(A[j])) * cpx(0, -0.5);
cpx b1 = (B[i] + conj(B[j])) * cpx(0.5, 0);
cpx b2 = (B[i] - conj(B[j])) * cpx(0, -0.5);
fa[i] = a1 * b1 + a2 * b2 * cpx(0, 1);
fb[i] = a1 * b2 + a2 * b1;
}
fft(fa, true);
fft(fb, true);
vector<int> res(need);
for (int i = 0; i < need; i++) {
long long aa = (long long)(fa[i].real() + 0.5);
long long bb = (long long)(fb[i].real() + 0.5);
long long cc = (long long)(fa[i].imag() + 0.5);
res[i] = (aa % m + (bb % m << 15) + (cc % m << 30)) % m;
}
return res;
}
constexpr int digits(int base) noexcept {
return base <= 1 ? 0 : 1 + digits(base / 10);
}
constexpr int base = 1000'000'000;
constexpr int base_digits = digits(base);
constexpr int fft_base = 10'000; // fft_base^2 * n / fft_base_digits <= 10^15 for double
constexpr int fft_base_digits = digits(fft_base);
struct bigint {
// value == 0 is represented by empty z
vector<int> z; // digits
// sign == 1 <==> value >= 0
// sign == -1 <==> value < 0
int sign;
bigint(long long v = 0) { *this = v; }
bigint &operator=(long long v) {
sign = v < 0 ? -1 : 1;
v *= sign;
z.clear();
for (; v > 0; v = v / base)
z.push_back((int)(v % base));
return *this;
}
bigint(const string &s) { read(s); }
bigint &operator+=(const bigint &other) {
if (sign == other.sign) {
for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
if (i == z.size())
z.push_back(0);
z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
carry = z[i] >= base;
if (carry)
z[i] -= base;
}
} else if (other != 0 /* prevent infinite loop */) {
*this -= -other;
}
return *this;
}
friend bigint operator+(bigint a, const bigint &b) {
a += b;
return a;
}
bigint &operator-=(const bigint &other) {
if (sign == other.sign) {
if ((sign == 1 && *this >= other) || (sign == -1 && *this <= other)) {
for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
carry = z[i] < 0;
if (carry)
z[i] += base;
}
trim();
} else {
*this = other - *this;
this->sign = -this->sign;
}
} else {
*this += -other;
}
return *this;
}
friend bigint operator-(bigint a, const bigint &b) {
a -= b;
return a;
}
bigint &operator*=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = 0, carry = 0; i < z.size() || carry; ++i) {
if (i == z.size())
z.push_back(0);
long long cur = (long long)z[i] * v + carry;
carry = (int)(cur / base);
z[i] = (int)(cur % base);
}
trim();
return *this;
}
bigint operator*(int v) const { return bigint(*this) *= v; }
friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
int norm = base / (b1.z.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.z.resize(a.z.size());
for (int i = (int)a.z.size() - 1; i >= 0; i--) {
r *= base;
r += a.z[i];
int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
int d = (int)(((long long)s1 * base + s2) / b.z.back());
r -= b * d;
while (r < 0)
r += b, --d;
q.z[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return {q, r / norm};
}
friend bigint sqrt(const bigint &a1) {
bigint a = a1;
while (a.z.empty() || a.z.size() % 2 == 1)
a.z.push_back(0);
int n = a.z.size();
int firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
int norm = base / (firstDigit + 1);
a *= norm;
a *= norm;
while (a.z.empty() || a.z.size() % 2 == 1)
a.z.push_back(0);
bigint r = (long long)a.z[n - 1] * base + a.z[n - 2];
firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
int q = firstDigit;
bigint res;
for (int j = n / 2 - 1; j >= 0; j--) {
for (;; --q) {
bigint r1 = (r - (res * 2 * base + q) * q) * base * base +
(j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
if (r1 >= 0) {
r = r1;
break;
}
}
res *= base;
res += q;
if (j > 0) {
int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
q = (int)(((long long)d1 * base * base + (long long)d2 * base + d3) / (firstDigit * 2));
}
}
res.trim();
return res / norm;
}
bigint operator/(const bigint &v) const { return divmod(*this, v).first; }
bigint operator%(const bigint &v) const { return divmod(*this, v).second; }
bigint &operator/=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = (int)z.size() - 1, rem = 0; i >= 0; --i) {
long long cur = z[i] + rem * (long long)base;
z[i] = (int)(cur / v);
rem = (int)(cur % v);
}
trim();
return *this;
}
bigint operator/(int v) const { return bigint(*this) /= v; }
int operator%(int v) const {
if (v < 0)
v = -v;
int m = 0;
for (int i = (int)z.size() - 1; i >= 0; --i)
m = (int)((z[i] + m * (long long)base) % v);
return m * sign;
}
bigint &operator*=(const bigint &v) {
*this = *this * v;
return *this;
}
bigint &operator/=(const bigint &v) {
*this = *this / v;
return *this;
}
bigint &operator%=(const bigint &v) {
*this = *this % v;
return *this;
}
bool operator<(const bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (z.size() != v.z.size())
return z.size() * sign < v.z.size() * v.sign;
for (int i = (int)z.size() - 1; i >= 0; i--)
if (z[i] != v.z[i])
return z[i] * sign < v.z[i] * sign;
return false;
}
bool operator>(const bigint &v) const { return v < *this; }
bool operator<=(const bigint &v) const { return !(v < *this); }
bool operator>=(const bigint &v) const { return !(*this < v); }
bool operator==(const bigint &v) const { return sign == v.sign && z == v.z; }
bool operator!=(const bigint &v) const { return !(*this == v); }
void trim() {
while (!z.empty() && z.back() == 0)
z.pop_back();
if (z.empty())
sign = 1;
}
bool isZero() const { return z.empty(); }
friend bigint operator-(bigint v) {
if (!v.z.empty())
v.sign = -v.sign;
return v;
}
bigint abs() const { return sign == 1 ? *this : -*this; }
long long longValue() const {
long long res = 0;
for (int i = (int)z.size() - 1; i >= 0; i--)
res = res * base + z[i];
return res * sign;
}
ldb ldbValue() const {
ldb res = 0;
for (int i = (int)z.size() - 1; i >= 0; i--)
res = res * base + z[i];
return res * sign;
}
friend bigint gcd(const bigint &a, const bigint &b) { return b.isZero() ? a : gcd(b, a % b); }
friend bigint lcm(const bigint &a, const bigint &b) { return a / gcd(a, b) * b; }
void read(const string &s) {
sign = 1;
z.clear();
int pos = 0;
while (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = (int)s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + s[j] - '0';
z.push_back(x);
}
trim();
}
friend istream &operator>>(istream &stream, bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
}
friend ostream &operator<<(ostream &stream, const bigint &v) {
if (v.sign == -1)
stream << '-';
stream << (v.z.empty() ? 0 : v.z.back());
for (int i = (int)v.z.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.z[i];
return stream;
}
static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < p.size(); i++)
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int v : a) {
cur += v * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int)cur);
while (!res.empty() && res.back() == 0)
res.pop_back();
return res;
}
bigint operator*(const bigint &v) const {
if (min(z.size(), v.z.size()) < 150)
return mul_simple(v);
bigint res;
res.sign = sign * v.sign;
res.z = multiply_bigint(convert_base(z, base_digits, fft_base_digits),
convert_base(v.z, base_digits, fft_base_digits), fft_base);
res.z = convert_base(res.z, fft_base_digits, base_digits);
res.trim();
return res;
}
bigint mul_simple(const bigint &v) const {
bigint res;
res.sign = sign * v.sign;
res.z.resize(z.size() + v.z.size());
for (int i = 0; i < z.size(); ++i)
if (z[i])
for (int j = 0, carry = 0; j < v.z.size() || carry; ++j) {
long long cur = res.z[i + j] + (long long)z[i] * (j < v.z.size() ? v.z[j] : 0) + carry;
carry = (int)(cur / base);
res.z[i + j] = (int)(cur % base);
}
res.trim();
return res;
}
};
//-----------------Big int-----------------------//
#define ll bigint
/*ll gcd(ll a,ll b){
return a==0?b:gcd(b%a,a);
}*/
ll myabs(ll a){return a<0?-a:a;}
struct frac{
ll p,q;
frac():p(0),q(1){}
frac(ll x):p(x),q(1){}
frac(ll a,ll b){
if(b<0)b=-b,a=-a;
ll g=gcd(myabs(a),b);
p=a/g;
q=b/g;
}
ldb to_ldb(){
return p.ldbValue()/q.ldbValue();
}
void Print(){
printf("%lf",to_ldb());
}
};
frac operator + (frac a,frac b){
return frac(a.p*b.q+b.p*a.q,a.q*b.q);
}
frac operator - (frac a,frac b){
return frac(a.p*b.q-b.p*a.q,a.q*b.q);
}
frac operator - (frac a){
return frac(-a.p,a.q);
}
frac operator * (frac a,frac b){
return frac(a.p*b.p,a.q*b.q);
}
frac operator * (frac a,ll b){
return frac(a.p*b,a.q);
}
frac operator / (frac a,frac b){
return frac(a.p*b.q,a.q*b.p);
}
frac operator / (frac a,ll b){
return frac(a.p,a.q*b);
}
bool operator < (frac a,frac b){
return a.p*b.q < b.p*a.q;
}
bool operator < (frac a,ll b){
return a.p < b*a.q;
}
bool operator == (frac a,frac b){
return a.p*b.q == b.p*a.q;
}
bool operator == (frac a,ll b){
return a.p == b*a.q;
}
bool operator <= (frac a,frac b){
return a<b || a==b;
}
bool operator <= (frac a,ll b){
return a<b || a==b;
}
int sgn(frac x){
if(x<0)return -1;
if(x==0)return 0;
return 1;
}
struct pt{
frac x,y;
pt():x(0),y(0){}
pt(ll a,ll b):x(a),y(b){}
pt(frac a,frac b):x(a),y(b){}
void Print(){
printf("(");
x.Print();
printf(", ");
y.Print();
printf(") ");
}
};
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator - (pt a){return pt(-a.x,-a.y);}
pt operator * (pt a,ll b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ll b){return pt(a.x/b,a.y/b);}
pt operator * (pt a,frac b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,frac b){return pt(a.x/b,a.y/b);}
frac cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
frac dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ldb dist(pt a,pt b){
ldb x1=a.x.to_ldb();
ldb y1=a.y.to_ldb();
ldb x2=b.x.to_ldb();
ldb y2=b.y.to_ldb();
ldb dx=x1-x2;
ldb dy=y1-y2;
return sqrt(dx*dx+dy*dy);
}
pt perp(pt a){return pt(-a.y,a.x);}
struct line{
pt from,to;
pt v;
frac c;
line(pt a,pt b){
from=a;
to=b;
v=b-a;
c=cross(v,a);
}
line(pt a,pt b,pt dir){
from=a;
to=b;
v=dir;
c=cross(v,a);
}
frac side(pt p){
return -cross(v,p)+c;
}
frac offs(pt p){
return dot(v,p);
}
bool onRay(pt p){
return offs(from)<offs(p);
}
bool onSegment(pt p){
return offs(from)<=offs(p) && offs(p)<=offs(to);
}
};
pt inter(line a,line b){
return (b.v*a.c-a.v*b.c)/cross(a.v,b.v);
}
bool parallel(line a,line b){
return cross(a.v,b.v)==0;
}
vector<pt> poly;
int n;
vector<line> cand;
line GetCand(pt from,pt to){
line a=line(from,to);
bool hasL=false,hasR=false;
pt L,R;
for(int i=0;i<n;i++){
int j=(i+1)%n;
int s1=sgn(a.side(poly[i]));
int s2=sgn(a.side(poly[j]));
if(s1!=0 && s2!=0){
if(s1!=s2){
pt p=inter(a,line(poly[i],poly[j]));
if(!(a.side(p)==0)){
a.from.Print();
a.to.Print();
printf(" x ");
poly[i].Print();
poly[j].Print();
printf(" => ");
p.Print();
printf("\n");
}
assert(a.side(p)==0);
if(a.onRay(p)){
if(!hasL || a.offs(p)<a.offs(L)){
L=p;hasL=true;
}
if(!hasR || a.offs(p)<a.offs(R)){
R=p;hasR=true;
}
}
}
}else if(s1==0 && s2==0){
}else{
pt p;
if(s1==0){
p=poly[i];
}else{
p=poly[j];
}
int s3=s1+s2;
if(a.onRay(p)){
if(s3==-1){
if(!hasL || a.offs(p)<a.offs(L)){
L=p;hasL=true;
}
}else{
if(!hasR || a.offs(p)<a.offs(R)){
R=p;hasR=true;
}
}
}
}
}
//printf("GetCand ");
//from.Print();
//to.Print();
//printf("%i %i\n",hasL,hasR);
//L.Print();
//R.Print();
//printf("\n");
if(!hasL && !hasR)return line(from,from);
if(!hasL)return line(from,R,to-from);
if(!hasR)return line(from,L,to-from);
if(a.offs(L)<a.offs(R)){
return line(from,R,to-from);
}else{
return line(from,L,to-from);
}
}
bool Inside(pt p){
int cnt=0;
for(int i=0;i<n;i++){
int j=(i+1)%n;
line seg=line(poly[i],poly[j]);
if(seg.side(p)==0 && seg.onSegment(p))return true;
cnt+=((p.y<poly[i].y)-(p.y<poly[j].y))*sgn(cross(poly[i]-p,poly[j]-p))>0;
}
return cnt%2==1;
}
pt S,E;
const int N=105;
const ldb inf=1e18;
ldb dp[N];
bool was[N];
vector<pair<int,ldb>> G[N];
int main(){
scanf("%i",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%i %i",&x,&y);
poly.pb(pt(x,y));
}
int sx,sy,ex,ey;
scanf("%i %i",&sx,&sy);
S=pt(sx,sy);
scanf("%i %i",&ex,&ey);
E=pt(ex,ey);
for(pt p:poly){
cand.pb(GetCand(E,p));
//cand.back().from.Print();
//cand.back().to.Print();
//printf("\n");
}
cand.pb(GetCand(E,S));
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
line seg=GetCand(poly[i],poly[j]);
ldb d=dist(poly[i],poly[j]);
//printf("Ray %i - %i: ",i+1,j+1);
//seg.to.Print();
//printf("\n");
if(seg.onSegment(poly[j]) && Inside((poly[i]+poly[j])/2)){
G[i].pb({j,d});
G[j].pb({i,d});
//printf("Edge\n");
}
}
}
for(int i=0;i<n;i++){
line seg=GetCand(S,poly[i]);
ldb d=dist(S,poly[i]);
//printf("Ray S - %i: ",i+1);
//seg.to.Print();
//printf("\n");
if(seg.onSegment(poly[i])){
G[n].pb({i,d});
//printf("Edge\n");
}
}
for(int i=0;i<n;i++)dp[i]=inf;
dp[n]=0;
while(true){
ldb now=inf;
int best=-1;
for(int j=0;j<=n;j++){
if(!was[j] && dp[j]<now){
now=dp[j];
best=j;
}
}
if(best==-1)break;
was[best]=true;
for(auto e:G[best]){
dp[e.first]=min(dp[e.first],dp[best]+e.second);
}
}
ldb ans=inf;
for(int i=0;i<=n;i++){
if(was[i]){
pt p=i==n?S:poly[i];
//if(i<n)printf("Try %i\n",i+1);
//else printf("Try S\n");
for(int j=0;j<cand.size();j++){
line seg=cand[j];
if(seg.v.x==0 && seg.v.y==0)continue;
//printf("Seg %i\n",j);
//seg.to.Print();
//printf("\n");
int s=sgn(seg.side(p));
//printf("%i\n",s);
if(s==0){
if(seg.onSegment(p)){
ans=min(ans,dp[i]);
//printf("ANS %.12lf\n",dp[i]);
}
}else{
pt dir=perp(seg.v);
if(s==-1)dir=-dir;
//printf("Dir ");
//seg.v.Print();
//dir.Print();
//printf("\n");
//printf("===================================\n");
line ray=GetCand(p,p+dir);
//printf("Perp ray ");
//ray.from.Print();
//ray.to.Print();
//printf("\n");
if(!parallel(ray,seg)){
pt o=inter(ray,seg);
if(seg.onSegment(o) && ray.onSegment(o)){
ans=min(ans,dp[i]+dist(p,o));
//printf("ANS %.12lf\n",dp[i]+dist(p,o));
}
}
ray=GetCand(p,seg.to);
if(ray.onSegment(seg.to) && Inside((p+seg.to)/2)){
ans=min(ans,dp[i]+dist(p,seg.to));
}
}
}
}
}
printf("%.12lf\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 342ms
memory: 3928kb
input:
15 13 7 20 20 39 20 49 7 73 13 100 5 117 38 98 20 80 20 66 40 68 20 51 20 41 39 22 48 2 39 10 20 104 20
output:
29.000000000000
result:
ok found '29.0000000', expected '29.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 402ms
memory: 3976kb
input:
16 39 2 48 22 39 41 20 51 20 68 40 66 20 80 20 98 38 117 5 100 13 73 7 49 19 39 20 23 20 20 7 13 20 10 20 104
output:
13.000000000000
result:
ok found '13.0000000', expected '13.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 384ms
memory: 3964kb
input:
16 13 33 20 60 23 66 39 97 49 105 73 166 100 205 117 272 98 216 80 180 66 172 68 156 51 122 41 121 22 92 2 44 10 40 104 228
output:
140.872282582487
result:
ok found '140.8722826', expected '140.8722826', error '0.0000000'
Test #4:
score: 0
Accepted
time: 538ms
memory: 4076kb
input:
16 64 17 50 28 67 23 65 18 77 4 88 20 78 10 70 29 61 28 47 32 54 17 43 13 35 20 41 30 27 20 42 6 81 12 33 23
output:
64.204537702523
result:
ok found '64.2045377', expected '64.2045377', error '0.0000000'
Test #5:
score: 0
Accepted
time: 498ms
memory: 3964kb
input:
16 64 17 50 28 67 23 65 18 77 4 88 20 78 10 70 29 61 28 47 32 54 17 43 13 35 20 41 30 27 20 42 6 33 23 81 12
output:
72.283498041177
result:
ok found '72.2834980', expected '72.2834980', error '0.0000000'
Test #6:
score: 0
Accepted
time: 74ms
memory: 3944kb
input:
7 76 8 389 215 691 19 407 331 489 397 300 403 363 334 126 60 393 370
output:
6.657917756511
result:
ok found '6.6579178', expected '6.6579178', error '0.0000000'
Test #7:
score: 0
Accepted
time: 5ms
memory: 4120kb
input:
3 0 1000 1000 0 1000 1000 567 578 589 601
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 5ms
memory: 3920kb
input:
3 0 1000 0 0 1000 0 366 366 367 366
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #9:
score: 0
Accepted
time: 34ms
memory: 4128kb
input:
5 50 93 278 178 199 300 596 362 208 519 421 388 142 153
output:
175.169759391735
result:
ok found '175.1697594', expected '175.1697594', error '0.0000000'
Test #10:
score: 0
Accepted
time: 85ms
memory: 4056kb
input:
7 50 93 278 178 199 300 401 312 483 162 596 362 208 519 488 252 142 153
output:
289.682139876890
result:
ok found '289.6821399', expected '289.6821399', error '0.0000000'
Test #11:
score: 0
Accepted
time: 74ms
memory: 3912kb
input:
8 10 10 40 25 20 25 20 35 12 23 30 23 10 20 5 40 15 15 19 26
output:
25.000000000000
result:
ok found '25.0000000', expected '25.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 133ms
memory: 3908kb
input:
9 5 1000 6 3 5 999 0 1000 0 0 500 2 500 0 1000 0 1000 1000 1 4 993 1
output:
5.101047906986
result:
ok found '5.1010479', expected '5.1010479', error '0.0000000'
Test #13:
score: -100
Time Limit Exceeded
input:
100 695 43 538 87 463 208 597 329 750 306 812 481 960 555 912 344 983 450 987 573 994 852 941 985 801 855 792 800 849 806 792 696 924 701 939 672 710 546 722 668 723 807 715 767 624 524 634 554 547 503 357 352 627 458 651 495 937 558 932 545 864 509 753 489 509 397 341 335 300 495 199 528 380 688 48...