QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357016#5104. Guardians of the GalleryTadijaSebezTL 538ms4128kbC++1421.3kb2024-03-18 17:31:032024-03-18 17:31:03

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 17:31:03]
  • 评测
  • 测评结果:TL
  • 用时:538ms
  • 内存:4128kb
  • [2024-03-18 17:31:03]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: