QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186292 | #5667. Meeting Places | BUET_POTATOES# | AC ✓ | 414ms | 70352kb | C++20 | 24.0kb | 2023-09-23 16:17:55 | 2023-09-23 16:17:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef double Tf; typedef double Ti;
const Tf PI = acos(-1), EPS = 1e-9;
int dcmp(Tf x) {return abs(x)<EPS? 0 :(x<0?-1:1);}
struct PT {
Ti x, y;
PT(Ti x = 0, Ti y = 0) : x(x), y(y) {}
PT operator + (const PT& u) const
{ return PT(x + u.x, y + u.y); }
PT operator - (const PT& u)
const { return PT(x - u.x, y - u.y); }
PT operator * (const long long u)
const { return PT(x * u, y * u); }
PT operator * (const Tf u)
const { return PT(x * u, y * u); }
PT operator / (const Tf u) const
{ return PT(x / u, y / u); }
bool operator == (const PT& u) const
{ return dcmp(x-u.x)==0 && dcmp(y-u.y)==0;}
bool operator != (const PT& u) const
{ return !(*this == u); }
bool operator < (const PT& u) const
{ return dcmp(x-u.x) < 0 ||
(dcmp(x-u.x) == 0 && dcmp(y-u.y) < 0);}
friend istream &operator >> (istream &is, PT &p)
{ return is >> p.x >> p.y; }
friend ostream &operator << (ostream &os,
const PT &p) {return os<<p.x<<" "<<p.y; }
};
Ti dot(PT a, PT b) { return a.x*b.x + a.y*b.y; }
Ti cross(PT a, PT b) { return a.x*b.y - a.y*b.x; }
Tf length(PT a) { return sqrt(dot(a, a)); }
Ti sqLength(PT a) { return dot(a, a); }
Tf distance(PT a, PT b) {return length(a-b);}
Tf angle(PT u) { return atan2(u.y, u.x); }
Tf angleBetween(PT a, PT b) { //in range [-PI, PI]
Tf ans = angle(b) - angle(a);
return ans <= -PI ? ans + 2*PI :
(ans > PI ? ans - 2*PI : ans);
}
PT rotate(PT a, Tf rad) {
static_assert(is_same<Tf, Ti>::value);
return PT(a.x * cos(rad) - a.y * sin(rad),
a.x * sin(rad) + a.y * cos(rad));
}
// Rotate(a, rad) where cos(rad)=co, sin(rad)=si
PT rotatePrecise(PT a, Tf co, Tf si) {
static_assert(is_same<Tf, Ti>::value);
return PT(a.x*co - a.y*si, a.y*co + a.x*si);
}
PT rotate90(PT a) { return PT(-a.y, a.x); }
PT scale(PT a, Tf s) {
static_assert(is_same<Tf, Ti>::value);
return a / length(a) * s;
}
PT normal(PT a) {
static_assert(is_same<Tf, Ti>::value);
Tf l = length(a); return PT(-a.y / l, a.x / l);
}
// returns 1/0/-1 if c is left/on/right of ab
int orient(PT a, PT b, PT c) {
return dcmp(cross(b - a, c - a));
}
///sort(v.begin(), v.end(),polarComp(O, dir))
struct polarComp {
PT O, dir;
polarComp(PT O = PT(0, 0), PT dir = PT(1, 0))
: O(O), dir(dir) {}
bool half(PT p) {
return dcmp(cross(dir, p)) < 0 ||
(dcmp(cross(dir, p))==0&&dcmp(dot(dir, p))>0);
}
bool operator()(PT p, PT q) {
return make_tuple(half(p-O), 0) <
make_tuple(half(q-O), cross(p-O, q-O));
}
};
struct Segment {
PT a, b;
Segment() {}
Segment(PT aa, PT bb) : a(aa), b(bb) {}
}; typedef Segment Line;
struct Circle {
PT o; Tf r;
Circle(PT o = PT(0, 0), Tf r = 0) : o(o),r(r) {}
bool contains(PT p) {
return dcmp(sqLength(p - o) - r * r) <= 0; }
PT point(Tf rad) {
static_assert(is_same<Tf, Ti>::value);
return PT(o.x+cos(rad)*r, o.y+sin(rad)*r);
}
Tf area(Tf rad = PI + PI) { return rad * r *r/2;}
Tf sector(Tf alpha) {
return r*r*0.5*(alpha-sin(alpha)); }
};
namespace Linear {
bool onSegment(PT p, Segment s) { ///Is p on S?
return dcmp(cross(s.a - p, s.b - p)) == 0 &&
dcmp(dot(s.a - p, s.b - p)) <= 0;
}
bool segmentsIntersect(Segment p, Segment q) {
if(onSegment(p.a,q)||onSegment(p.b,q))return 1;
if(onSegment(q.a,p)||onSegment(q.b,p))return 1;
Ti c1 = cross(p.b - p.a, q.a - p.a);
Ti c2 = cross(p.b - p.a, q.b - p.a);
Ti c3 = cross(q.b - q.a, p.a - q.a);
Ti c4 = cross(q.b - q.a, p.b - q.a);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool linesParallel(Line p, Line q) {
return dcmp(cross(p.b - p.a, q.b - q.a)) == 0;
}
//returns if lines (p, p+v) && (q, q+ w) intersect
bool lineLineIntersect(PT p,PT v,PT q,PT w,PT&o) {
static_assert(is_same<Tf, Ti>::value);
if(dcmp(cross(v, w)) == 0) return false;
PT u = p - q; o = p + v*(cross(w,u)/cross(v,w));
return true;
}
bool lineLineIntersect(Line p, Line q, PT& o) {
return lineLineIntersect(p.a, p.b - p.a, q.a,
q.b - q.a, o);
}
Tf distancePointLine(PT p, Line l) {
return abs(cross(l.b-l.a, p-l.a)/length(l.b-l.a));
}
Tf distancePointSegment(PT p, Segment s) {
if(s.a == s.b) return length(p - s.a);
PT v1 = s.b - s.a, v2 = p - s.a, v3 = p - s.b;
if(dcmp(dot(v1, v2)) < 0) return length(v2);
else if(dcmp(dot(v1, v3))>0) return length(v3);
else return abs(cross(v1, v2) / length(v1));
}
Tf distanceSegmentSegment(Segment p, Segment q) {
if(segmentsIntersect(p, q)) return 0;
Tf ans = distancePointSegment(p.a, q);
ans = min(ans, distancePointSegment(p.b, q));
ans = min(ans, distancePointSegment(q.a, p));
ans = min(ans, distancePointSegment(q.b, p));
return ans;
}
PT projectPointLine(PT p, Line l) {
static_assert(is_same<Tf, Ti>::value);
PT v = l.b - l.a;
return l.a + v * ((Tf) dot(v, p-l.a)/dot(v, v));
} } // namespace Linear
typedef vector<PT> Polygon;
namespace Polygonal {
/// cannot be all collinear
Polygon RemoveCollinear(const Polygon& poly) {
Polygon ret;
int n = poly.size();
for(int i = 0; i < n; i++) {
PT a = poly[i];
PT b = poly[(i + 1) % n];
PT c = poly[(i + 2) % n];
if(dcmp(cross(b-a, c-b))!=0 && (ret.empty() ||
b != ret.back())) ret.push_back(b);
}
return ret;
}
Tf signedPolygonArea(const Polygon &p) {
Tf ret = 0;
for(int i = 0; i < (int) p.size() - 1; i++)
ret += cross(p[i]-p[0], p[i+1]-p[0]);
return ret / 2;
}
///fails if all collinear and remove = TRUE
Polygon convexHull(Polygon p, bool remRedundant) {
int check = remRedundant ? 0 : -1;
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int n = p.size(); Polygon ch(n+n);
int m = 0; // preparing lower hull
for(int i = 0; i < n; i++) {
while(m > 1 && dcmp(cross(ch[m - 1]-ch[m - 2],
p[i] - ch[m - 1])) <= check) m--;
ch[m++] = p[i];
}
int k = m; // preparing upper hull
for(int i = n - 2; i >= 0; i--) {
while(m > k && dcmp(cross(ch[m - 1] - ch[m-2],
p[i] - ch[m - 2])) <= check) m--;
ch[m++] = p[i];
}
if(n > 1) m--; ch.resize(m);
return ch;
}
// returns inside = -1, on = 0, outside = 1
int pointInPolygon(const Polygon &p, PT o) {
using Linear::onSegment; int wn=0, n = p.size();
for(int i = 0; i < n; i++) {
int j = (i + 1) % n; if(onSegment(o,
Segment(p[i], p[j])) || o == p[i]) return 0;
int k = dcmp(cross(p[j] - p[i], o - p[i]));
int d1=dcmp(p[i].y-o.y), d2=dcmp(p[j].y-o.y);
if(k > 0 && d1 <= 0 && d2 > 0) wn++;
if(k < 0 && d2 <= 0 && d1 > 0) wn--;
}
return wn ? -1 : 1;
}
// returns (longest segment, total length)
pair<Tf, Tf> linePolygonIntersection(Line l,
const Polygon &p) {
using Linear::lineLineIntersect;
int n = p.size(); vector<pair<Tf, int>> ev;
for(int i=0; i<n; ++i) {
PT a = p[i], b = p[(i+1)%n], z = p[(i-1+n)%n];
int ora=orient(l.a,l.b,a), orb =
orient(l.a,l.b,b), orz=orient(l.a,l.b,z);
if(!ora) {
Tf d = dot(a - l.a, l.b - l.a);
if(orz && orb) {
if(orz != orb) ev.emplace_back(d, 0);
//else // PT Touch
} else if(orz) ev.emplace_back(d, orz);
else if(orb) ev.emplace_back(d, orb);
}
else if(ora == -orb) {
PT ins;
lineLineIntersect(l, Line(a, b), ins);
ev.emplace_back(dot(ins-l.a, l.b-l.a),0);
}
}
sort(ev.begin(), ev.end());
Tf ans = 0, len = 0, last = 0, tot = 0;
bool active = false; int sign = 0;
for(auto &qq : ev) {
int tp = qq.second;
Tf d = qq.first; ///current Seg is (last, d)
if(sign) { ///On Border
len+=d-last; tot+=d-last; ans=max(ans,len);
if(tp != sign) active = !active;
sign = 0;
}
else {
if(active) { ///Strictly Inside
len+=d-last;tot+=d-last;ans=max(ans,len);
}
if(tp == 0) active=!active; else sign = tp;
}
last = d; if(!active) len = 0;
}
ans /= length(l.b-l.a); tot /= length(l.b-l.a);
return {ans, tot};
} } // namespace Polygonal
namespace Convex {
Polygon minkowskiSum(Polygon A, Polygon B){
int n = A.size(), m = B.size();
rotate(A.begin(),
min_element(A.begin(), A.end()), A.end());
rotate(B.begin(),
min_element(B.begin(), B.end()), B.end());
A.push_back(A[0]); B.push_back(B[0]);
for(int i = 0; i < n; i++) A[i] = A[i+1] - A[i];
for(int i = 0; i < m; i++) B[i] = B[i+1] - B[i];
Polygon C(n+m+1); C[0] = A.back() + B.back();
merge(A.begin(), A.end()-1, B.begin(),B.end()-1,
C.begin()+1, polarComp(PT(0, 0), PT(0, -1)));
for(int i=1; i<C.size(); i++) C[i]=C[i]+C[i-1];
C.pop_back(); return C;
}
//{min area, min perimeter) rectangle containing p
pair<Tf,Tf>rotatingCalipersBBox(const Polygon &p){
using Linear::distancePointLine;
static_assert(is_same<Tf, Ti>::value);
int n = p.size(); int l = 1, r = 1, j = 1;
Tf area = 1e100; Tf perimeter = 1e100;
for(int i = 0; i < n; i++) {
PT v=(p[(i+1)%n]-p[i])/length(p[(i+1)%n]-p[i]);
while(dcmp(dot(v, p[r%n] - p[i]) -
dot(v, p[(r+1)%n] - p[i])) < 0) r++;
while(j < r || dcmp(cross(v, p[j%n] - p[i]) -
cross(v, p[(j+1)%n] - p[i])) < 0) j++;
while(l < j || dcmp(dot(v, p[l%n] - p[i]) -
dot(v, p[(l+1)%n] - p[i])) > 0) l++;
Tf w = dot(v,p[r%n]-p[i])-dot(v,p[l%n]-p[i]);
Tf h = distancePointLine(p[j%n],
Line(p[i], p[(i+1)%n]));
area = min(area, w * h);
perimeter = min(perimeter, 2 * w + 2 * h);
} return make_pair(area, perimeter);
}
// returns the left half of u on left on ray ab
Polygon cutPolygon(Polygon u, PT a, PT b) {
using Linear::lineLineIntersect;
using Linear::onSegment;
Polygon ret; int n = u.size();
for(int i = 0; i < n; i++) {
PT c = u[i], d = u[(i + 1) % n];
if(dcmp(cross(b-a, c-a))>=0) ret.push_back(c);
if(dcmp(cross(b-a, d-c)) != 0) {
PT t; lineLineIntersect(a, b-a, c, d-c, t);
if(onSegment(t,Segment(c,d)))ret.push_back(t);
}
} return ret;
}
bool pointInTriangle(PT a, PT b, PT c, PT p) {
return dcmp(cross(b - a, p - a)) >= 0
&& dcmp(cross(c - b, p - b)) >= 0
&& dcmp(cross(a - c, p - c)) >= 0;
}
int pointInConvexPolygon(const Polygon &pt, PT p){
int n = pt.size(); assert(n >= 3);
int lo = 1, hi = n - 1;
while(hi - lo > 1) {
int mid = (lo + hi) / 2;
if(dcmp(cross(pt[mid]-pt[0], p - pt[0])) > 0)
lo = mid;
else hi = mid;
}
bool in=pointInTriangle(pt[0],pt[lo],pt[hi],p);
if(!in) return 1;
if(dcmp(cross(pt[lo]-pt[lo-1],p-pt[lo-1]))==0)
return 0; if(dcmp(cross(pt[hi]-pt[lo],
p-pt[lo]))==0) return 0; if(dcmp(cross(pt[hi]-
pt[(hi+1)%n], p-pt[(hi+1)%n]))==0) return 0;
return -1;
}
// most extreme Point in the direction u
int extremePoint(const Polygon &poly, PT u) {
int n = (int) poly.size();
int a = 0, b = n;
while(b - a > 1) {
int c = (a + b) / 2;
if(dcmp(dot(poly[c]-poly[(c+1)%n], u))>=0 &&
dcmp(dot(poly[c]-poly[(c-1+n)%n], u))>=0) {
return c; }
bool a_up=dcmp(dot(poly[(a+1)%n]-poly[a],u))>=0;
bool c_up=dcmp(dot(poly[(c+1)%n]-poly[c],u))>=0;
bool a_above_c=dcmp(dot(poly[a]-poly[c],u))>0;
if(a_up && !c_up) b = c;
else if(!a_up && c_up) a = c;
else if(a_up && c_up) {
if(a_above_c) b = c; else a = c;
} else {
if(!a_above_c) b = c; else a = c;
}
}
if(dcmp(dot(poly[a]-poly[(a+1)%n],u))>0 &&
dcmp(dot(poly[a]-poly[(a-1+n)%n],u))>0)
return a;
return b % n;
}
// return list of segs of p that touch/intersect l
// the i'th segment is (p[i], p[(i + 1)%|p|])
// #1 If a side is collinear, only that returned
// #2 If l goes through p[i], ith segment is added
vector<int> lineConvexPolyIntersection(
const Polygon &p, Line l) {
assert((int) p.size() >= 3); assert(l.a != l.b);
int n = p.size(); vector<int> ret;
PT v = l.b - l.a;
int lf = extremePoint(p, rotate90(v));
int rt = extremePoint(p, rotate90(v) * Ti(-1));
int olf = orient(l.a, l.b, p[lf]);
int ort = orient(l.a, l.b, p[rt]);
if(!olf || !ort) {
int idx = (!olf ? lf : rt);
if(orient(l.a, l.b, p[(idx - 1 + n) % n])==0)
ret.push_back((idx - 1 + n) % n);
else ret.push_back(idx);
return ret;
}
if(olf == ort) return ret;
for(int i=0; i<2; ++i) {
int lo = i ? rt : lf, hi = i ? lf : rt;
int olo = i ? ort : olf;
while(true) {
int gap = (hi - lo + n) % n;
if(gap < 2) break;
int mid = (lo + gap / 2) % n;
int omid = orient(l.a, l.b, p[mid]);
if(!omid) {lo = mid;break;}
if(omid == olo) lo = mid;
else hi = mid;
} ret.push_back(lo);
} return ret;
}
// [ACW, CW] tangent pair from an external point
constexpr int CW = -1, ACW = 1;
bool isGood(PT u, PT v, PT Q, int dir) {
return orient(Q, u, v) != -dir; }
PT better(PT u, PT v, PT Q, int dir) {
return orient(Q, u, v) == dir ? u : v; }
PT pointPolyTangent(const Polygon &pt, PT Q,
int dir, int lo, int hi) {
while(hi - lo > 1) {
int mid = (lo + hi) / 2;
bool pvs = isGood(pt[mid], pt[mid-1], Q, dir);
bool nxt = isGood(pt[mid], pt[mid+1], Q, dir);
if(pvs && nxt) return pt[mid];
if(!(pvs || nxt)) {
PT p1 = pointPolyTangent(pt,Q,dir,mid+1,hi);
PT p2 = pointPolyTangent(pt,Q,dir,lo,mid-1);
return better(p1, p2, Q, dir);
}
if(!pvs) {
if(orient(Q,pt[mid],pt[lo])==dir) hi=mid-1;
else if(better(pt[lo],pt[hi],Q,dir)==pt[lo])
hi = mid - 1; else lo = mid + 1;
}
if(!nxt) {
if(orient(Q,pt[mid],pt[lo])==dir) lo=mid+1;
else if(better(pt[lo],pt[hi],Q,dir)==pt[lo])
hi = mid - 1; else lo = mid + 1;
}
}
PT ret = pt[lo];
for(int i = lo + 1; i <= hi; i++)
ret = better(ret, pt[i], Q, dir);
return ret;
}
// [ACW, CW] Tangent
pair<PT,PT> pointPolyTangents(
const Polygon &pt,PT Q) {
int n = pt.size();
PT acw_tan = pointPolyTangent(pt, Q, ACW,0,n-1);
PT cw_tan = pointPolyTangent(pt, Q, CW, 0, n-1);
return make_pair(acw_tan, cw_tan);
} }
namespace Circular {
// returns intersections in order of ray (l.a,l.b)
vector<PT>circleLineIntersection(Circle c,Line l){
static_assert(is_same<Tf, Ti>::value);
vector<PT> ret;
PT b = l.b - l.a, a = l.a - c.o;
Tf A = dot(b, b), B = dot(a, b);
Tf C = dot(a, a) - c.r * c.r, D = B*B - A*C;
if (D < -EPS) return ret;
ret.push_back(l.a + b * (-B-sqrt(D + EPS)) / A);
if (D > EPS)
ret.push_back(l.a + b * (-B + sqrt(D)) / A);
return ret;
}
// circle(c.o, c.r) x triangle(c.o,s.a,s.b) (ccw)
Tf circleTriInterArea(Circle c, Segment s){
using Linear::distancePointSegment;
Tf OA = length(c.o-s.a), OB = length(c.o-s.b);
if(dcmp(distancePointSegment(c.o, s) - c.r) >= 0)
return angleBetween(s.a-c.o,s.b-c.o)*c.r*c.r/2;
if(dcmp(OA - c.r) <= 0 && dcmp(OB - c.r) <= 0)
return cross(c.o - s.b, s.a - s.b) / 2.0;
vector<PT> Sect = circleLineIntersection(c, s);
return circleTriInterArea(c,Segment(s.a,Sect[0]))
+circleTriInterArea(c,Segment(Sect[0],Sect[1]))
+ circleTriInterArea(c,Segment(Sect[1],s.b));
}
Tf circlePolyIntersectionArea(Circle c, Polygon p){
Tf res = 0;
int n = p.size();
for(int i = 0; i < n; ++i)
res +=circleTriInterArea(c,
Segment(p[i], p[(i + 1) % n]));
return abs(res);
}
// locates circle c2 relative to c1: intersect = 0
// inside = -2, inside touch = -1,
// outside touch = 1, outside = 2
int circleCirclePosition(Circle c1, Circle c2) {
Tf d = length(c1.o - c2.o);
int in = dcmp(d - abs(c1.r - c2.r)),
ex = dcmp(d - (c1.r + c2.r));
return in<0?-2:in==0?-1: ex==0?1: ex>0?2:0;
}
vector<PT> circleCircleInter(Circle c1, Circle c2){
static_assert(is_same<Tf, Ti>::value);
vector<PT> ret;
Tf d = length(c1.o - c2.o);
if(dcmp(d) == 0) return ret;
if(dcmp(c1.r + c2.r - d) < 0) return ret;
if(dcmp(abs(c1.r - c2.r) - d) > 0) return ret;
PT v = c2.o - c1.o;
Tf co = (c1.r * c1.r + sqLength(v) - c2.r*c2.r)
/ (2 * c1.r * length(v));
Tf si = sqrt(abs(1.0 - co * co));
PT p1 = scale(rotatePrecise(v,co,-si),c1.r)+c1.o;
PT p2 = scale(rotatePrecise(v,co,si),c1.r)+c1.o;
ret.push_back(p1);
if(p1 != p2) ret.push_back(p2); return ret;
}
Tf circleCircleInterArea(Circle c1, Circle c2) {
PT AB = c2.o - c1.o; Tf d = length(AB);
if(d >= c1.r + c2.r) return 0;
if(d + c1.r <= c2.r) return PI * c1.r * c1.r;
if(d + c2.r <= c1.r) return PI * c2.r * c2.r;
Tf alpha1 = acos((c1.r*c1.r + d*d - c2.r*c2.r)
/ (2.0 * c1.r * d));
Tf alpha2 = acos((c2.r*c2.r + d*d - c1.r*c1.r)
/ (2.0 * c2.r * d));
return c1.sector(2*alpha1)+c2.sector(2*alpha2);
}
// returns tangents from a point p to circle c
vector<PT> pointCircleTangents(PT p, Circle c) {
static_assert(is_same<Tf, Ti>::value);
vector<PT> ret;PT u = c.o - p; Tf d = length(u);
if(d < c.r) ;
else if(dcmp(d - c.r) == 0) {
ret = { rotate(u, PI / 2) }; }
else {
Tf ang = asin(c.r / d);
ret = { rotate(u, -ang), rotate(u, ang) };
} return ret;
}
//returns points on tangents that touches circle c
vector<PT>pointCircleTangencyPoints(PT p,Circle c){
static_assert(is_same<Tf, Ti>::value);
PT u = p - c.o; Tf d = length(u);
if(d < c.r) return {};
else if(dcmp(d - c.r) == 0) return {c.o + u};
else {
Tf ang = acos(c.r / d); u = u/length(u) * c.r;
return{c.o+rotate(u,-ang), c.o+rotate(u,ang)};
}
}
// finds a, b st a[i] on c1, b[i] on c2, Segment
// a[i], b[i] touches c1, c2. if c1, c2 touch at x
// (x, x) is also returned, -1 returned if c1 = c2
int circleCircleTangencyPoints(Circle c1,Circle c2,
vector<PT> &a, vector<PT> &b) {
a.clear(), b.clear(); int cnt = 0;
if(dcmp(c1.r-c2.r)<0) {swap(c1, c2);swap(a, b);}
Tf d2 = sqLength(c1.o - c2.o);
Tf rdif = c1.r - c2.r, rsum = c1.r + c2.r;
if(dcmp(d2 - rdif * rdif) < 0) return 0;
if(dcmp(d2)==0 && dcmp(c1.r-c2.r)==0) return -1;
Tf base = angle(c2.o - c1.o);
if(dcmp(d2 - rdif * rdif) == 0) {
a.push_back(c1.point(base));
b.push_back(c2.point(base));
cnt++; return cnt;
}
Tf ang = acos((c1.r - c2.r) / sqrt(d2));
a.push_back(c1.point(base + ang));
b.push_back(c2.point(base + ang)); cnt++;
a.push_back(c1.point(base - ang));
b.push_back(c2.point(base - ang)); cnt++;
if(dcmp(d2 - rsum * rsum) == 0) {
a.push_back(c1.point(base));
b.push_back(c2.point(PI + base)); cnt++;
}
else if(dcmp(d2 - rsum * rsum) > 0) {
Tf ang = acos((c1.r + c2.r) / sqrt(d2));
a.push_back(c1.point(base + ang));
b.push_back(c2.point(PI + base + ang)); cnt++;
a.push_back(c1.point(base - ang));
b.push_back(c2.point(PI + base - ang)); cnt++;
} return cnt;
} } // namespace Circular
const int N = 2e3 + 5;
double cost[N][N];
int done[N][N];
namespace EnclosingCircle{
// returns false if points are collinear
bool inCircle(PT a, PT b, PT c, Circle &p) {
using Linear::distancePointLine;
static_assert(is_same<Tf, Ti>::value);
if(orient(a, b, c) == 0) return false;
Tf u=length(b-c), v=length(c-a), w=length(a-b);
p.o = (a * u + b * v + c * w) / (u + v + w);
p.r = distancePointLine(p.o, Line(a, b));
return true;
}
// set of points A(x, y) st PA : QA = rp : rq
Circle apolloniusCircle(PT P, PT Q, Tf rp, Tf rq){
static_assert(is_same<Tf, Ti>::value);
rq *= rq; rp *= rp; Tf a=rq-rp; assert(dcmp(a));
Tf g = (rq*P.x-rp*Q.x)/a, h = (rq*P.y-rp*Q.y)/a;
Tf c = (rq*P.x*P.x - rp*Q.x*Q.x +
rq*P.y*P.y - rp*Q.y*Q.y)/a;
PT o(g, h); Tf R = sqrt(g * g + h * h - c);
return Circle(o, R);
}
// returns false if points are collinear
bool circumCircle(PT a, PT b, PT c, Circle &p) {
using Linear::lineLineIntersect;
if(orient(a, b, c) == 0) return false;
PT d = (a + b) / 2, e = (a + c) / 2;
PT vd = rotate90(b - a), ve = rotate90(a - c);
bool f = lineLineIntersect(d, vd, e, ve, p.o);
if(f) p.r = length(a - p.o);
return f;
}
/// finds a circle that goes all of p, |p| <= 3.
Circle boundary(const vector<PT> &p) {
Circle ret; int sz = p.size();
if(sz == 0) ret.r = 0;
else if(sz == 1) ret.o = p[0], ret.r = 0;
else if(sz == 2) ret.o = (p[0] + p[1]) / 2,
ret.r = length(p[0] - p[1]) / 2;
else if(!circumCircle(p[0],p[1],p[2],ret))
ret.r = 0;
return ret;
}
/// Min circle enclosing p[fr.....n-1],
///with points in b on the boundary, |b| <= 3.
Circle welzl(const vector<PT> &p,
int fr, vector<PT> &b, bool save) {
if(save)assert(b.empty());
if(fr >= (int) p.size() || b.size() == 3){
Circle c = boundary(b);
return c;
}
Circle c = welzl(p, fr + 1, b, save);
if(!c.contains(p[fr])) {
b.push_back(p[fr]); c = welzl(p, fr + 1, b, false);
b.pop_back();
}
if(save){
// if(fr == 0 && p.size() == 2){
// cout << "ASHSE" << endl;
// }
cost[fr][p.size() - 1] = c.r;
}
return c;
}
/// MEC of p, using weizl's algo. amortized O(n).
void MEC(vector<PT> p) {
// random_shuffle(p.begin(), p.end());
int n = p.size();
for(int i = 0; i < n; i++){
vector<PT> q;
// cout << p.size() << endl;
welzl(p, 0, q, true);
p.pop_back();
}
} }
const int M = 233811181;
const int MOD = (1LL << 31) - 1;
using LL = long long;
Tf dp[N];
int cnt[N];
Tf dp2[N][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<PT> v(n);
cin >> v[0].x;
for(int i = 0; i < n; i++){
v[i].y = ((LL)v[i].x * M + 1) % MOD;
if(i != n - 1){
v[i + 1].x = ((LL)v[i].y * M + 1) % MOD;
}
}
// for(int i = 0; i < 5; i++)cout << v[i].x << ' ' << v[i].y << endl;
EnclosingCircle::MEC(v);
// for(int i = 0; i < n; i++){
// for(int j = i; j < n; j++)cout << cost[i][j] << ' ';
// cout << endl;
// }
// Tf lo = 0, hi = 1e10;
// auto solve = [&](Tf m){
// for(int i = 0; i < n; i++){
// dp[i] = cost[0][i] + m;
// cnt[i] = 1;
// for(int j = 0; j < i; j++){
// if(dp[i] > dp[j] + cost[j + 1][i] + m){
// dp[i] = dp[j] + cost[j + 1][i] + m;
// cnt[i] = cnt[j] + 1;
// }
// }
// }
//// cout << m * n << ' ' << dp[n - 1] << endl;
//// cout << cnt[n - 1] << endl;
// return make_pair(dp[n - 1], cnt[n - 1]);
// };
//
// for(int i = 0; i < 200; i++){
// Tf mid = (lo + hi) / 2;
// if(solve(mid).second > k){
// lo = mid;
// }else{
// hi = mid;
// }
// }
// cout << cost[0][n - 1] << endl;
// cout << hi << endl;
// cout << solve(hi).first << endl;
// cout << solve(hi).second << endl;
// cout << fixed << setprecision(10) << solve(hi).first - k * hi << "\n";
cout << fixed << setprecision(10);
if(n < 200){
for(int i = 0; i < n; i++){
dp2[i][1] = cost[0][i];
for(int j = 2; j <= k; j++){
dp2[i][j] = dp2[i][j - 1];
for(int k = 0; k < i; k++){
dp2[i][j] = min(dp2[i][j], dp2[k][j - 1] + cost[k + 1][i]);
}
}
}
cout << dp2[n - 1][k] << "\n";
}else{
for(int i = 0; i < n; i++){
dp2[i][1] = cost[0][i];
for(int j = 2; j <= k; j++){
dp2[i][j] = dp2[i][j - 1];
for(int k = max(0, i - 20); k < i; k++){
dp2[i][j] = min(dp2[i][j], dp2[k][j - 1] + cost[k + 1][i]);
}
}
}
Tf ans = dp2[n - 1][k];
int t = n - k + 1;
for(int i = 0; i + t <= n; i++){
ans = min(ans, cost[i][i + t - 1]);
}
cout << ans << "\n";
}
}
/*
5 5 213
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6404kb
input:
100 23 213
output:
1319350480.8007326126
result:
ok found '1319350480.8007326', expected '1319350480.8007326', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5980kb
input:
10 1 1060
output:
1042753143.3451676369
result:
ok found '1042753143.3451676', expected '1042753143.3451676', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 6008kb
input:
10 10 2373
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5940kb
input:
10 2 3396
output:
1236610536.9469230175
result:
ok found '1236610536.9469230', expected '1236610536.9469230', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
10 3 1998
output:
973790809.8224442005
result:
ok found '973790809.8224442', expected '973790809.8224442', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 6000kb
input:
10 4 562
output:
910867389.9069329500
result:
ok found '910867389.9069330', expected '910867389.9069330', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
10 5 6048
output:
818240814.7105150223
result:
ok found '818240814.7105150', expected '818240814.7105150', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 6096kb
input:
10 6 2524
output:
500106979.3467762470
result:
ok found '500106979.3467762', expected '500106979.3467762', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
10 7 5415
output:
559478971.4320058823
result:
ok found '559478971.4320059', expected '559478971.4320059', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 6012kb
input:
10 8 1438
output:
500309745.4627699852
result:
ok found '500309745.4627700', expected '500309745.4627700', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
10 9 3172
output:
162279748.8753451705
result:
ok found '162279748.8753452', expected '162279748.8753452', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 10280kb
input:
100 1 8316
output:
1320052902.1522903442
result:
ok found '1320052902.1522903', expected '1320052902.1522903', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 10372kb
input:
100 100 4179
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 10456kb
input:
100 12 3405
output:
1329687126.1304550171
result:
ok found '1329687126.1304550', expected '1329687126.1304548', error '0.0000000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 10144kb
input:
100 16 8378
output:
1338056514.4842693806
result:
ok found '1338056514.4842694', expected '1338056514.4842694', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 10180kb
input:
100 2 1858
output:
1310392496.1430580616
result:
ok found '1310392496.1430581', expected '1310392496.1430581', error '0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 10180kb
input:
100 25 4596
output:
1440464106.6229298115
result:
ok found '1440464106.6229298', expected '1440464106.6229298', error '0.0000000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 6328kb
input:
100 3 5633
output:
1399621082.6142737865
result:
ok found '1399621082.6142738', expected '1399621082.6142738', error '0.0000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 10340kb
input:
100 32 7827
output:
1342073760.5322329998
result:
ok found '1342073760.5322330', expected '1342073760.5322330', error '0.0000000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 10348kb
input:
100 4 3693
output:
1339808706.7098689079
result:
ok found '1339808706.7098689', expected '1339808706.7098689', error '0.0000000'
Test #21:
score: 0
Accepted
time: 2ms
memory: 10152kb
input:
100 5 2252
output:
1394874243.5057041645
result:
ok found '1394874243.5057042', expected '1394874243.5057042', error '0.0000000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 6444kb
input:
100 50 4254
output:
1322809748.4052834511
result:
ok found '1322809748.4052835', expected '1322809748.4052832', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 6380kb
input:
100 6 53
output:
1364441356.1700987816
result:
ok found '1364441356.1700988', expected '1364441356.1700988', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 10256kb
input:
100 64 4337
output:
1180754550.2422840595
result:
ok found '1180754550.2422841', expected '1180754550.2422838', error '0.0000000'
Test #25:
score: 0
Accepted
time: 2ms
memory: 10284kb
input:
100 7 5366
output:
1423557626.3586797714
result:
ok found '1423557626.3586798', expected '1423557626.3586798', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 10104kb
input:
100 8 8509
output:
1353289305.3519957066
result:
ok found '1353289305.3519957', expected '1353289305.3519957', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 10072kb
input:
100 9 1423
output:
1228887266.5661668777
result:
ok found '1228887266.5661669', expected '1228887266.5661671', error '0.0000000'
Test #28:
score: 0
Accepted
time: 3ms
memory: 10224kb
input:
100 91 4806
output:
656574218.5086754560
result:
ok found '656574218.5086755', expected '656574218.5086756', error '0.0000000'
Test #29:
score: 0
Accepted
time: 3ms
memory: 10556kb
input:
100 92 4024
output:
794693428.6162240505
result:
ok found '794693428.6162241', expected '794693428.6162238', error '0.0000000'
Test #30:
score: 0
Accepted
time: 3ms
memory: 10440kb
input:
100 93 606
output:
677641787.4863121510
result:
ok found '677641787.4863122', expected '677641787.4863122', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 10416kb
input:
100 94 7265
output:
686423239.2626028061
result:
ok found '686423239.2626028', expected '686423239.2626028', error '0.0000000'
Test #32:
score: 0
Accepted
time: 0ms
memory: 10440kb
input:
100 95 8469
output:
328187125.9235950708
result:
ok found '328187125.9235951', expected '328187125.9235951', error '0.0000000'
Test #33:
score: 0
Accepted
time: 3ms
memory: 10528kb
input:
100 96 1079
output:
492964787.6259085536
result:
ok found '492964787.6259086', expected '492964787.6259086', error '0.0000000'
Test #34:
score: 0
Accepted
time: 0ms
memory: 10212kb
input:
100 97 5453
output:
258652807.7906563878
result:
ok found '258652807.7906564', expected '258652807.7906564', error '0.0000000'
Test #35:
score: 0
Accepted
time: 2ms
memory: 8504kb
input:
100 98 1778
output:
159490192.1188907623
result:
ok found '159490192.1188908', expected '159490192.1188908', error '0.0000000'
Test #36:
score: 0
Accepted
time: 0ms
memory: 10260kb
input:
100 99 1825
output:
33793756.3289980441
result:
ok found '33793756.3289980', expected '33793756.3289980', error '0.0000000'
Test #37:
score: 0
Accepted
time: 66ms
memory: 35132kb
input:
1000 1 2453
output:
1486878333.2858574390
result:
ok found '1486878333.2858574', expected '1486878333.2858574', error '0.0000000'
Test #38:
score: 0
Accepted
time: 64ms
memory: 39084kb
input:
1000 1000 1798
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #39:
score: 0
Accepted
time: 42ms
memory: 38956kb
input:
1000 125 43
output:
1474031969.5174233913
result:
ok found '1474031969.5174234', expected '1474031969.5174232', error '0.0000000'
Test #40:
score: 0
Accepted
time: 86ms
memory: 37268kb
input:
1000 128 8107
output:
1440374614.9391977787
result:
ok found '1440374614.9391978', expected '1440374614.9391975', error '0.0000000'
Test #41:
score: 0
Accepted
time: 47ms
memory: 39048kb
input:
1000 15 6639
output:
1491336935.5536251068
result:
ok found '1491336935.5536251', expected '1491336935.5536251', error '0.0000000'
Test #42:
score: 0
Accepted
time: 39ms
memory: 35148kb
input:
1000 16 1251
output:
1445211807.1160962582
result:
ok found '1445211807.1160963', expected '1445211807.1160963', error '0.0000000'
Test #43:
score: 0
Accepted
time: 81ms
memory: 39200kb
input:
1000 2 1303
output:
1468989868.6486022472
result:
ok found '1468989868.6486022', expected '1468989868.6486022', error '0.0000000'
Test #44:
score: 0
Accepted
time: 47ms
memory: 38896kb
input:
1000 250 4457
output:
1487674970.7660157681
result:
ok found '1487674970.7660158', expected '1487674970.7660158', error '0.0000000'
Test #45:
score: 0
Accepted
time: 40ms
memory: 39148kb
input:
1000 256 4135
output:
1474218271.5140771866
result:
ok found '1474218271.5140772', expected '1474218271.5140772', error '0.0000000'
Test #46:
score: 0
Accepted
time: 34ms
memory: 35276kb
input:
1000 3 713
output:
1482496228.9904775620
result:
ok found '1482496228.9904776', expected '1482496228.9904778', error '0.0000000'
Test #47:
score: 0
Accepted
time: 50ms
memory: 39164kb
input:
1000 31 8139
output:
1494361943.4799194336
result:
ok found '1494361943.4799194', expected '1494361943.4799194', error '0.0000000'
Test #48:
score: 0
Accepted
time: 53ms
memory: 38972kb
input:
1000 32 7916
output:
1499333171.0938646793
result:
ok found '1499333171.0938647', expected '1499333171.0938647', error '0.0000000'
Test #49:
score: 0
Accepted
time: 77ms
memory: 39136kb
input:
1000 4 2432
output:
1455826569.0394101143
result:
ok found '1455826569.0394101', expected '1455826569.0394101', error '0.0000000'
Test #50:
score: 0
Accepted
time: 48ms
memory: 38924kb
input:
1000 5 2457
output:
1452189628.1967139244
result:
ok found '1452189628.1967139', expected '1452189628.1967139', error '0.0000000'
Test #51:
score: 0
Accepted
time: 71ms
memory: 39412kb
input:
1000 500 8734
output:
1432279300.5662786961
result:
ok found '1432279300.5662787', expected '1432279300.5662787', error '0.0000000'
Test #52:
score: 0
Accepted
time: 30ms
memory: 37516kb
input:
1000 512 1866
output:
1446804508.0351865292
result:
ok found '1446804508.0351865', expected '1446804508.0351865', error '0.0000000'
Test #53:
score: 0
Accepted
time: 37ms
memory: 39180kb
input:
1000 6 1580
output:
1490178756.8566033840
result:
ok found '1490178756.8566034', expected '1490178756.8566034', error '0.0000000'
Test #54:
score: 0
Accepted
time: 45ms
memory: 39084kb
input:
1000 62 3047
output:
1482100829.6467108727
result:
ok found '1482100829.6467109', expected '1482100829.6467109', error '0.0000000'
Test #55:
score: 0
Accepted
time: 37ms
memory: 38996kb
input:
1000 64 4836
output:
1441850815.8553614616
result:
ok found '1441850815.8553615', expected '1441850815.8553615', error '0.0000000'
Test #56:
score: 0
Accepted
time: 46ms
memory: 39180kb
input:
1000 7 5269
output:
1473104490.7287983894
result:
ok found '1473104490.7287984', expected '1473104490.7287984', error '0.0000000'
Test #57:
score: 0
Accepted
time: 42ms
memory: 38968kb
input:
1000 8 2649
output:
1459133296.6066234112
result:
ok found '1459133296.6066234', expected '1459133296.6066234', error '0.0000000'
Test #58:
score: 0
Accepted
time: 36ms
memory: 35220kb
input:
1000 9 3999
output:
1482914523.3807039261
result:
ok found '1482914523.3807039', expected '1482914523.3807039', error '0.0000000'
Test #59:
score: 0
Accepted
time: 84ms
memory: 35960kb
input:
1000 991 3610
output:
295501032.4780874252
result:
ok found '295501032.4780874', expected '295501032.4780874', error '0.0000000'
Test #60:
score: 0
Accepted
time: 87ms
memory: 39576kb
input:
1000 992 3030
output:
337274092.6540381312
result:
ok found '337274092.6540381', expected '337274092.6540381', error '0.0000000'
Test #61:
score: 0
Accepted
time: 95ms
memory: 35824kb
input:
1000 993 6980
output:
222375113.1057986021
result:
ok found '222375113.1057986', expected '222375113.1057986', error '0.0000000'
Test #62:
score: 0
Accepted
time: 90ms
memory: 35932kb
input:
1000 994 7222
output:
218007091.6933040917
result:
ok found '218007091.6933041', expected '218007091.6933041', error '0.0000000'
Test #63:
score: 0
Accepted
time: 79ms
memory: 39148kb
input:
1000 995 1323
output:
169577520.2236528993
result:
ok found '169577520.2236529', expected '169577520.2236529', error '0.0000000'
Test #64:
score: 0
Accepted
time: 74ms
memory: 39036kb
input:
1000 996 2761
output:
135524743.9114488363
result:
ok found '135524743.9114488', expected '135524743.9114488', error '0.0000000'
Test #65:
score: 0
Accepted
time: 113ms
memory: 36048kb
input:
1000 997 4946
output:
87043806.4227920771
result:
ok found '87043806.4227921', expected '87043806.4227921', error '0.0000000'
Test #66:
score: 0
Accepted
time: 63ms
memory: 35796kb
input:
1000 998 842
output:
24094936.5511916876
result:
ok found '24094936.5511917', expected '24094936.5511917', error '0.0000000'
Test #67:
score: 0
Accepted
time: 81ms
memory: 39124kb
input:
1000 999 5078
output:
4597519.0646550339
result:
ok found '4597519.0646550', expected '4597519.0646550', error '0.0000000'
Test #68:
score: 0
Accepted
time: 171ms
memory: 66384kb
input:
2000 1 2633
output:
1502350354.4995269775
result:
ok found '1502350354.4995270', expected '1502350354.4995270', error '0.0000000'
Test #69:
score: 0
Accepted
time: 202ms
memory: 67076kb
input:
2000 1000 6248
output:
1469507093.4042112827
result:
ok found '1469507093.4042113', expected '1469507093.4042110', error '0.0000000'
Test #70:
score: 0
Accepted
time: 242ms
memory: 68176kb
input:
2000 1024 2507
output:
1448066815.3184788227
result:
ok found '1448066815.3184788', expected '1448066815.3184788', error '0.0000000'
Test #71:
score: 0
Accepted
time: 142ms
memory: 66520kb
input:
2000 125 3002
output:
1476846542.0318911076
result:
ok found '1476846542.0318911', expected '1476846542.0318909', error '0.0000000'
Test #72:
score: 0
Accepted
time: 414ms
memory: 66404kb
input:
2000 128 5622
output:
1464957942.6400380135
result:
ok found '1464957942.6400380', expected '1464957942.6400380', error '0.0000000'
Test #73:
score: 0
Accepted
time: 219ms
memory: 66364kb
input:
2000 15 5891
output:
1490626300.1558670998
result:
ok found '1490626300.1558671', expected '1490626300.1558671', error '0.0000000'
Test #74:
score: 0
Accepted
time: 149ms
memory: 69928kb
input:
2000 16 1750
output:
1504400245.4149806499
result:
ok found '1504400245.4149806', expected '1504400245.4149806', error '0.0000000'
Test #75:
score: 0
Accepted
time: 305ms
memory: 67160kb
input:
2000 1990 6698
output:
313951388.4046511054
result:
ok found '313951388.4046511', expected '313951388.4046511', error '0.0000000'
Test #76:
score: 0
Accepted
time: 223ms
memory: 67212kb
input:
2000 1991 80
output:
248800118.6793060303
result:
ok found '248800118.6793060', expected '248800118.6793060', error '0.0000000'
Test #77:
score: 0
Accepted
time: 303ms
memory: 67052kb
input:
2000 1992 4802
output:
257156356.5216794908
result:
ok found '257156356.5216795', expected '257156356.5216795', error '0.0000000'
Test #78:
score: 0
Accepted
time: 303ms
memory: 67096kb
input:
2000 1993 169
output:
197117968.4482247829
result:
ok found '197117968.4482248', expected '197117968.4482248', error '0.0000000'
Test #79:
score: 0
Accepted
time: 383ms
memory: 70048kb
input:
2000 1994 6269
output:
109695555.8088501096
result:
ok found '109695555.8088501', expected '109695555.8088501', error '0.0000000'
Test #80:
score: 0
Accepted
time: 411ms
memory: 67780kb
input:
2000 1995 3452
output:
179563229.3967843056
result:
ok found '179563229.3967843', expected '179563229.3967843', error '0.0000000'
Test #81:
score: 0
Accepted
time: 300ms
memory: 70352kb
input:
2000 1996 2191
output:
84783513.6455895752
result:
ok found '84783513.6455896', expected '84783513.6455896', error '0.0000000'
Test #82:
score: 0
Accepted
time: 294ms
memory: 67404kb
input:
2000 1997 7803
output:
53635859.3399899751
result:
ok found '53635859.3399900', expected '53635859.3399900', error '0.0000000'
Test #83:
score: 0
Accepted
time: 227ms
memory: 67708kb
input:
2000 1998 8341
output:
33466185.8149442300
result:
ok found '33466185.8149442', expected '33466185.8149442', error '0.0000000'
Test #84:
score: 0
Accepted
time: 281ms
memory: 67048kb
input:
2000 1999 6773
output:
2608075.4652832611
result:
ok found '2608075.4652833', expected '2608075.4652833', error '0.0000000'
Test #85:
score: 0
Accepted
time: 144ms
memory: 66388kb
input:
2000 2 4496
output:
1484602254.1310012341
result:
ok found '1484602254.1310012', expected '1484602254.1310012', error '0.0000000'
Test #86:
score: 0
Accepted
time: 280ms
memory: 67092kb
input:
2000 2000 5384
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #87:
score: 0
Accepted
time: 299ms
memory: 66472kb
input:
2000 250 1029
output:
1465117434.0631005764
result:
ok found '1465117434.0631006', expected '1465117434.0631006', error '0.0000000'
Test #88:
score: 0
Accepted
time: 222ms
memory: 66600kb
input:
2000 256 5220
output:
1481878242.2184739113
result:
ok found '1481878242.2184739', expected '1481878242.2184739', error '0.0000000'
Test #89:
score: 0
Accepted
time: 123ms
memory: 66332kb
input:
2000 3 8403
output:
1489320436.4318530560
result:
ok found '1489320436.4318531', expected '1489320436.4318533', error '0.0000000'
Test #90:
score: 0
Accepted
time: 138ms
memory: 66452kb
input:
2000 31 6950
output:
1477330995.2251310349
result:
ok found '1477330995.2251310', expected '1477330995.2251310', error '0.0000000'
Test #91:
score: 0
Accepted
time: 216ms
memory: 67812kb
input:
2000 32 3632
output:
1496222504.6490063667
result:
ok found '1496222504.6490064', expected '1496222504.6490064', error '0.0000000'
Test #92:
score: 0
Accepted
time: 136ms
memory: 66292kb
input:
2000 4 2987
output:
1477889007.5054593086
result:
ok found '1477889007.5054593', expected '1477889007.5054593', error '0.0000000'
Test #93:
score: 0
Accepted
time: 205ms
memory: 69908kb
input:
2000 5 2580
output:
1485468254.7374951839
result:
ok found '1485468254.7374952', expected '1485468254.7374952', error '0.0000000'
Test #94:
score: 0
Accepted
time: 172ms
memory: 66716kb
input:
2000 500 6270
output:
1475788271.0275988579
result:
ok found '1475788271.0275989', expected '1475788271.0275989', error '0.0000000'
Test #95:
score: 0
Accepted
time: 195ms
memory: 66712kb
input:
2000 512 1864
output:
1470340599.4749855995
result:
ok found '1470340599.4749856', expected '1470340599.4749856', error '0.0000000'
Test #96:
score: 0
Accepted
time: 252ms
memory: 69916kb
input:
2000 6 8814
output:
1497075189.0134959221
result:
ok found '1497075189.0134959', expected '1497075189.0134962', error '0.0000000'
Test #97:
score: 0
Accepted
time: 136ms
memory: 66424kb
input:
2000 62 4139
output:
1490927650.9732120037
result:
ok found '1490927650.9732120', expected '1490927650.9732120', error '0.0000000'
Test #98:
score: 0
Accepted
time: 121ms
memory: 66400kb
input:
2000 64 7700
output:
1494910912.6137833595
result:
ok found '1494910912.6137834', expected '1494910912.6137834', error '0.0000000'
Test #99:
score: 0
Accepted
time: 243ms
memory: 69916kb
input:
2000 7 8304
output:
1488325857.8219897747
result:
ok found '1488325857.8219898', expected '1488325857.8219898', error '0.0000000'
Test #100:
score: 0
Accepted
time: 173ms
memory: 66340kb
input:
2000 8 7774
output:
1507136513.1715590954
result:
ok found '1507136513.1715591', expected '1507136513.1715591', error '0.0000000'
Test #101:
score: 0
Accepted
time: 206ms
memory: 69836kb
input:
2000 9 2618
output:
1492019659.0373163223
result:
ok found '1492019659.0373163', expected '1492019659.0373163', error '0.0000000'
Test #102:
score: 0
Accepted
time: 11ms
memory: 18772kb
input:
500 1 7674
output:
1463672939.7812500000
result:
ok found '1463672939.7812500', expected '1463672939.7812500', error '0.0000000'
Test #103:
score: 0
Accepted
time: 15ms
memory: 22708kb
input:
500 125 1629
output:
1420736329.0838274956
result:
ok found '1420736329.0838275', expected '1420736329.0838273', error '0.0000000'
Test #104:
score: 0
Accepted
time: 15ms
memory: 22704kb
input:
500 15 7376
output:
1465677415.5063879490
result:
ok found '1465677415.5063879', expected '1465677415.5063879', error '0.0000000'
Test #105:
score: 0
Accepted
time: 15ms
memory: 22572kb
input:
500 250 5627
output:
1411074935.8823580742
result:
ok found '1411074935.8823581', expected '1411074935.8823581', error '0.0000000'
Test #106:
score: 0
Accepted
time: 14ms
memory: 18776kb
input:
500 3 2245
output:
1437079231.5409810543
result:
ok found '1437079231.5409811', expected '1437079231.5409811', error '0.0000000'
Test #107:
score: 0
Accepted
time: 14ms
memory: 22684kb
input:
500 31 8072
output:
1487957912.0314612389
result:
ok found '1487957912.0314612', expected '1487957912.0314612', error '0.0000000'
Test #108:
score: 0
Accepted
time: 12ms
memory: 22392kb
input:
500 62 2415
output:
1454787477.6493773460
result:
ok found '1454787477.6493773', expected '1454787477.6493773', error '0.0000000'
Test #109:
score: 0
Accepted
time: 10ms
memory: 22540kb
input:
500 7 1586
output:
1459900114.7046606541
result:
ok found '1459900114.7046607', expected '1459900114.7046607', error '0.0000000'