QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291122 | #3246. 喵喵花園 | MoRanSky | AC ✓ | 615ms | 167508kb | C++23 | 7.0kb | 2023-12-26 04:58:53 | 2023-12-26 04:58:54 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define y1 dmytxdy
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
template <typename T> bool chkMax(T &x, T y) {
return (y > x) ? x = y, 1 : 0;
}
template <typename T> bool chkMin(T &x, T y) {
return (y < x) ? x = y, 1 : 0;
}
template <typename T> void inline read(T &x) {
int f = 1;
x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
f = -1;
s = getchar();
}
while (s <= '9' && s >= '0')
x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x, T y) {
return x > y ? x = y, 1 : 0;
}
template <typename T> bool chkmax(T &x, T y) {
return x < y ? x = y, 1 : 0;
}
int readint() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
const int N = 1005;
const long double eps = 1e-6;
typedef pair<long double, long double> PDD;
int inline cmp(long double x, long double y) {
if (fabs(x - y) < eps)
return 0;
return x < y ? -1 : 1;
}
long double inline cross(PDD a, PDD b) {
return a.fi * b.se - a.se * b.fi;
}
PDD operator - (const PDD &a, const PDD &b) {
return make_pair(a.fi - b.fi, a.se - b.se);
}
PDD operator + (const PDD &a, const PDD &b) {
return make_pair(a.fi + b.fi, a.se + b.se);
}
PDD operator / (const PDD &a, long double b) {
return make_pair(a.fi / b, a.se / b);
}
PDD operator * (const PDD &a, long double b) {
return make_pair(a.fi * b, a.se * b);
}
long double inline area(PDD a, PDD b, PDD c) {
return cross(b - a, c - a);
}
long double inline dot(PDD a, PDD b) {
return a.fi * b.fi + a.se * b.se;
}
long double inline len(PDD a) {
return sqrt(dot(a, a));
}
long double inline project(PDD a, PDD b, PDD c) {
return dot(b - a, c - a) / len(b - a);
}
long double inline dist(PDD a, PDD b) {
return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
// 顺时针转 x
PDD inline rotate(PDD a, long double x) {
return make_pair(cos(x) * a.fi + sin(x) * a.se, -sin(x) * a.fi + cos(x) * a.se);
}
PDD inline norm(PDD a) {
return a / len(a);
}
long double angle(PDD a, PDD b) {
return acos(dot(a, b) / len(a) / len(b));
}
int n, k;
PDD a[N];
long double L = 0;
PDD x1[N], y1[N];
long double lim[N];
struct Line {
int op;
long double L, kx, bx, ky, by;
bool operator < (const Line &b) const {
return L < b.L;
}
};
struct AC {
int o;
long double x, A, B, C;
bool operator < (const AC &b) const {
return x < b.x;
}
} ct[N];
vector<AC> e;
vector<Line> X;
long double inline mod(long double k) {
if (k >= L)
k -= L;
return k;
}
void bd(long double o, int op) {
for (int i = 1; i <= n; i++) {
if (lim[i] + o <= L && lim[i + 1] + o > L) {
X.pb((Line) {
op, lim[i] + o, x1[i].fi, x1[i].se - x1[i].fi *o, y1[i].fi, y1[i].se - y1[i].fi *o
});
X.pb((Line) {
op, 0, x1[i].fi, x1[i].se - x1[i].fi * (o - L), y1[i].fi, y1[i].se - y1[i].fi * (o - L)
});
// puts("tototot\n");
} else if (lim[i] + o <= L) {
X.pb((Line) {
op, lim[i] + o, x1[i].fi, x1[i].se - x1[i].fi *o, y1[i].fi, y1[i].se - y1[i].fi *o
});
} else {
X.pb((Line) {
op, lim[i] + o - L, x1[i].fi, x1[i].se - x1[i].fi * (o - L), y1[i].fi, y1[i].se - y1[i].fi * (o - L)
});
}
}
}
Line cur[2];
long double A, B, C, ans = 1e18, le, re;
void inline calc(long double x) {
if (cmp(x, le) == -1 || cmp(x, re) == 1)
return;
long double val = x * x * A + B * x + C;
//if (val < 0) return;
chkMin(ans, val);
}
void inline upd() {
calc(le);
calc(re);
calc(-B / A / 2);
}
int main() {
//freopen("1.in", "r", stdin);
n = readint();
k = readint();
for (int i = 1; i <= n; i++)
a[i].fi = readint(), a[i].se = readint();
a[n + 1] = a[1];
for (int i = 1; i <= n; i++)
L += dist(a[i], a[i + 1]);
long double now = 0;
long double D = L / k;
for (int i = 1; i <= n; i++) {
long double len = dist(a[i], a[i + 1]);
x1[i] = mp((a[i + 1].fi - a[i].fi) / len, a[i].fi);
y1[i] = mp((a[i + 1].se - a[i].se) / len, a[i].se);
x1[i].se -= x1[i].fi * now;
y1[i].se -= y1[i].fi * now;
lim[i] = now;
// cout << x1[i].fi << " " << x1[i].se << "---" << y1[i].fi << " " << y1[i].se << " ji\n";
now += len;
}
lim[n + 1] = now;
//cout << D <<" ??aaa\n";
for (int i = 0; i < k; i++) {
X.clear();
long double B = D * i, A = D * (i + 1);
if (i == k - 1)
A = 0;
bd(A, 0);
bd(B, 1);
//cout << " now it show time for " << A << " " << B << "??\n";
sort(X.begin(), X.end());
for (int j = 0; j < X.size(); j++) {
Line o = X[j];
cur[o.op] = o;
if (j + 1 < X.size() && !cmp(X[j].L, X[j + 1].L))
continue;
// cout << o.L << "->>\n" << cur[0].kx << " " << cur[0].bx << " " << cur[0].ky << " " << cur[0].by << endl;
// cout << o.L << "->>\n" << cur[1].kx << " " << cur[1].bx << " " << cur[1].ky << " " << cur[1].by << endl;
// cout << 0 << " " << o.L << "->>\n" << cur[0].kx * o.L + cur[0].bx << " " << cur[0].ky * o.L + cur[0].by << endl;
// cout << 1 << " "<< o.L << "->>\n" << cur[1].kx * o.L + cur[1].bx << " " << cur[1].ky * o.L + cur[1].by << endl;
e.pb((AC) {
i, o.L, (cur[0].kx * cur[1].ky - cur[1].kx * cur[0].ky),
cur[0].kx *cur[1].by + cur[0].bx *cur[1].ky - (cur[1].kx * cur[0].by + cur[1].bx * cur[0].ky),
cur[0].bx *cur[1].by - cur[1].bx *cur[0].by
});
}
}
sort(e.begin(), e.end());
for (int i = 0; i < e.size(); i++) {
int u = e[i].o;
A -= ct[u].A, B -= ct[u].B, C -= ct[u].C;
ct[u] = e[i];
A += ct[u].A, B += ct[u].B, C += ct[u].C;
if (i + 1 < e.size() && !cmp(e[i].x, e[i + 1].x))
continue;
le = e[i].x, re = L;
if (i + 1 < e.size())
re = e[i + 1].x;
// cout << i << " " << le << " " << re << "zjsw??\n";
upd();
}
printf("%.10Lf\n", ans / 2);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 485ms
memory: 167216kb
input:
1000 800 -99983 -1896 -99971 -2447 -99942 -3427 -99935 -3623 -99923 -3942 -99902 -4444 -99864 -5228 -99835 -5757 -99827 -5896 -99815 -6095 -99811 -6160 -99801 -6317 -99795 -6411 -99732 -7330 -99699 -7765 -99687 -7919 -99642 -8464 -99610 -8830 -99587 -9087 -99538 -9611 -99526 -9734 -99495 -10047 -994...
output:
31414852000.4136614799
result:
ok found '31414852000.413661957', expected '31414852000.414176941', error '0.000000000'
Test #2:
score: 0
Accepted
time: 521ms
memory: 167508kb
input:
1000 900 -99999 -632 -99993 -1258 -99990 -1472 -99986 -1724 -99981 -1997 -99957 -2961 -99955 -3024 -99949 -3211 -99932 -3712 -99908 -4311 -99895 -4599 -99861 -5290 -99835 -5757 -99806 -6239 -99791 -6476 -99750 -7078 -99707 -7660 -99608 -8855 -99572 -9249 -99539 -9599 -99505 -9947 -99493 -10066 -9938...
output:
31415015242.8877042774
result:
ok found '31415015242.887702942', expected '31415015242.887584686', error '0.000000000'
Test #3:
score: 0
Accepted
time: 615ms
memory: 167316kb
input:
1000 1000 -99997 -883 -99992 -1336 -99990 -1474 -99986 -1723 -99713 -7581 -99700 -7752 -99660 -8251 -99604 -8901 -99545 -9536 -99494 -10057 -99436 -10612 -99351 -11383 -99240 -12313 -99192 -12692 -99100 -13393 -99072 -13599 -99015 -14008 -98973 -14302 -98825 -15291 -98783 -15560 -98725 -15924 -98687...
output:
31414938256.4498835802
result:
ok found '31414938256.449882507', expected '31414938256.450866699', error '0.000000000'
Test #4:
score: 0
Accepted
time: 252ms
memory: 85392kb
input:
900 500 -100000 -378 -99990 -1474 -99987 -1657 -99971 -2447 -99968 -2567 -99909 -4273 -99870 -5111 -99857 -5362 -99843 -5619 -99673 -8089 -99644 -8442 -99605 -8890 -99545 -9536 -99412 -10838 -99377 -11153 -99148 -13034 -99130 -13170 -99079 -13548 -99002 -14098 -98810 -15388 -98338 -18160 -98252 -186...
output:
31414085412.4212222416
result:
ok found '31414085412.421222687', expected '31414085412.421134949', error '0.000000000'
Test #5:
score: 0
Accepted
time: 219ms
memory: 85476kb
input:
900 400 -100000 -337 -99999 -575 -99997 -875 -99996 -991 -99995 -1080 -99991 -1400 -99990 -1469 -99967 -2600 -99965 -2675 -99944 -3367 -99896 -4576 -99873 -5052 -99802 -6305 -99690 -7879 -99654 -8319 -99576 -9210 -99507 -9927 -99430 -10671 -99404 -10909 -99317 -11676 -99105 -13357 -99076 -13570 -990...
output:
31413800407.1723493319
result:
ok found '31413800407.172348022', expected '31413800407.172279358', error '0.000000000'
Test #6:
score: 0
Accepted
time: 411ms
memory: 167348kb
input:
900 800 -99998 -758 -99995 -1096 -99988 -1611 -99981 -1998 -99971 -2447 -99963 -2752 -99862 -5261 -99728 -7384 -99524 -9755 -99511 -9885 -99490 -10094 -99452 -10462 -99397 -10974 -99382 -11109 -99255 -12191 -99074 -13582 -98847 -15148 -98690 -16139 -98542 -17019 -98508 -17214 -98461 -17482 -98377 -1...
output:
31414646664.5007420778
result:
ok found '31414646664.500743866', expected '31414646664.500938416', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 7360kb
input:
1000 10 -99998 -754 -99991 -1400 -99986 -1728 -99981 -2000 -99973 -2361 -99969 -2528 -99959 -2893 -99928 -3808 -99915 -4142 -99870 -5115 -99846 -5565 -99834 -5775 -99723 -7451 -99690 -7879 -99643 -8452 -99625 -8664 -99606 -8879 -99509 -9908 -99289 -11910 -99194 -12679 -98942 -14515 -98847 -15147 -98...
output:
29387236138.6524098460
result:
ok found '29387236138.652408600', expected '29387236138.652404785', error '0.000000000'
Test #8:
score: 0
Accepted
time: 4ms
memory: 10516kb
input:
1000 20 -99998 -766 -99988 -1579 -99945 -3345 -99915 -4134 -99854 -5418 -99760 -6937 -99709 -7634 -99623 -8684 -99563 -9349 -99403 -10918 -99368 -11232 -99345 -11435 -99327 -11590 -99233 -12370 -99086 -13496 -99054 -13729 -99041 -13822 -98939 -14535 -98910 -14731 -98851 -15122 -98846 -15155 -98791 -...
output:
30900099346.9495120049
result:
ok found '30900099346.949512482', expected '30900099346.949504852', error '0.000000000'
Test #9:
score: 0
Accepted
time: 17ms
memory: 9436kb
input:
1000 30 -99991 -1389 -99970 -2490 -99957 -2963 -99937 -3574 -99933 -3685 -99929 -3789 -99871 -5095 -99789 -6508 -99776 -6705 -99760 -6938 -99731 -7343 -99723 -7452 -99642 -8464 -99599 -8956 -99451 -10474 -99427 -10699 -99338 -11494 -99294 -11869 -99270 -12067 -99201 -12623 -99193 -12686 -99169 -1287...
output:
31185342172.6591391321
result:
ok found '31185342172.659137726', expected '31185342172.659126282', error '0.000000000'
Test #10:
score: 0
Accepted
time: 24ms
memory: 14956kb
input:
1000 40 -99999 -616 -99993 -1240 -99989 -1527 -99975 -2271 -99957 -2954 -99925 -3887 -99904 -4397 -99880 -4918 -99838 -5707 -99790 -6493 -99763 -6893 -99743 -7178 -99729 -7370 -99713 -7584 -99668 -8152 -99648 -8393 -99603 -8909 -99469 -10298 -99241 -12305 -99167 -12888 -99114 -13288 -99085 -13504 -9...
output:
31285949928.7094558477
result:
ok found '31285949928.709457397', expected '31285949928.709457397', error '0.000000000'
Test #11:
score: 0
Accepted
time: 25ms
memory: 14820kb
input:
1000 50 -99999 -569 -99998 -734 -99988 -1610 -99957 -2964 -99943 -3399 -99941 -3461 -99926 -3858 -99887 -4772 -99884 -4834 -99852 -5457 -99821 -5989 -99805 -6257 -99785 -6560 -99729 -7370 -99683 -7968 -99634 -8553 -99612 -8807 -99366 -11251 -99278 -12003 -99223 -12450 -99189 -12717 -98924 -14635 -98...
output:
31331270922.4949191809
result:
ok found '31331270922.494918823', expected '31331270922.494922638', error '0.000000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
10 7 -97003 -24299 -89014 -45570 -24303 -97003 -3451 -99941 30342 -95286 99989 1429 77069 63720 23803 97125 -97452 22434 -99819 6019
output:
22074403211.2198350430
result:
ok found '22074403211.219833374', expected '22074403211.219829559', error '0.000000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4568kb
input:
99 69 -99999 -511 -99998 -704 -99694 -7827 -97628 -21653 -96532 -26109 -95683 -29068 -95604 -29327 -95333 -30197 -94390 -33026 -93663 -35034 -89230 -45145 -88157 -47207 -84909 -52827 -84336 -53737 -83533 -54976 -79833 -60223 -79323 -60893 -76198 -64761 -75696 -65347 -74794 -66378 -67390 -73883 -5915...
output:
31247417729.6599788070
result:
ok found '31247417729.659976959', expected '31247417729.659965515', error '0.000000000'
Test #14:
score: 0
Accepted
time: 6ms
memory: 6840kb
input:
100 100 -99990 -1440 -99479 -10203 -97709 -21284 -97042 -24144 -94178 -33626 -92144 -38853 -90337 -42888 -88565 -46436 -82545 -56448 -82088 -57112 -79241 -61000 -74743 -66436 -71625 -69785 -70900 -70522 -70015 -71400 -67477 -73804 -64539 -76386 -49557 -86858 -46685 -88434 -30940 -95094 -26367 -96462...
output:
31316997599.7958639860
result:
ok found '31316997599.795864105', expected '31316997599.795856476', error '0.000000000'
Test #15:
score: 0
Accepted
time: 102ms
memory: 45844kb
input:
500 400 -99998 -773 -99972 -2391 -99966 -2640 -99958 -2927 -99955 -3032 -99905 -4379 -99900 -4492 -99700 -7750 -99603 -8911 -99566 -9316 -99507 -9927 -99357 -11326 -99351 -11378 -99153 -12996 -99062 -13670 -98932 -14580 -98836 -15218 -98204 -18872 -97858 -20591 -97700 -21327 -97593 -21813 -97563 -21...
output:
31410954295.3885459900
result:
ok found '31410954295.388545990', expected '31410954295.388881683', error '0.000000000'
Test #16:
score: 0
Accepted
time: 169ms
memory: 85508kb
input:
1000 300 -99998 -766 -99996 -978 -99993 -1243 -99973 -2357 -99969 -2527 -99955 -3029 -99941 -3464 -99929 -3786 -99920 -4018 -99913 -4187 -99880 -4918 -99825 -5929 -99821 -5996 -99793 -6438 -99724 -7431 -99685 -7942 -99664 -8198 -99637 -8524 -99582 -9144 -99369 -11223 -99282 -11969 -99218 -12489 -992...
output:
31412738461.6591799259
result:
ok found '31412738461.659179688', expected '31412738461.659622192', error '0.000000000'
Test #17:
score: 0
Accepted
time: 3ms
memory: 4860kb
input:
1000 5 -99997 -819 -99992 -1341 -99985 -1772 -99978 -2139 -99967 -2599 -99947 -3283 -99942 -3431 -99912 -4207 -99890 -4710 -99875 -5016 -99838 -5707 -99800 -6336 -99765 -6862 -99723 -7448 -99649 -8381 -99621 -8707 -99500 -9997 -99439 -10587 -99296 -11851 -99251 -12223 -99030 -13899 -98892 -14850 -98...
output:
23774219173.3595492020
result:
ok found '23774219173.359550476', expected '23774219173.359542847', error '0.000000000'
Test #18:
score: 0
Accepted
time: 282ms
memory: 85300kb
input:
1000 500 -100000 -365 -99996 -969 -99990 -1476 -99982 -1942 -99973 -2366 -99971 -2448 -99965 -2680 -99952 -3127 -99941 -3459 -99927 -3845 -99897 -4554 -99887 -4768 -99857 -5363 -99816 -6079 -99766 -6852 -99748 -7106 -99705 -7680 -99685 -7941 -99676 -8055 -99638 -8513 -99584 -9120 -99570 -9274 -99499...
output:
31414386060.3031560741
result:
ok found '31414386060.303157806', expected '31414386060.303081512', error '0.000000000'