QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#193129 | #7229. Lines | jeffqi# | RE | 1842ms | 6408kb | C++20 | 3.6kb | 2023-09-30 16:25:50 | 2023-09-30 16:25:50 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;
namespace qiqi {
const double eps = 1e-10;
int cmp(double x) {
return x > eps ? 1 : x < -eps ? -1 : 0;
}
template<class T>
struct Point {
T x;
T y;
Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {}
template<class U>
operator Point<U>() {
return Point<U>(U(x), U(y));
}
Point &operator+=(Point p) & {
x += p.x;
y += p.y;
return *this;
}
Point &operator-=(Point p) & {
x -= p.x;
y -= p.y;
return *this;
}
Point &operator*=(T v) & {
x *= v;
y *= v;
return *this;
}
Point &operator/=(T v) & {
x /= v;
y /= v;
return *this;
}
Point operator-() const {
return Point(-x, -y);
}
friend Point operator+(Point a, Point b) {
return a += b;
}
friend Point operator-(Point a, Point b) {
return a -= b;
}
friend Point operator*(Point a, T b) {
return a *= b;
}
friend Point operator/(Point a, T b) {
return a /= b;
}
friend Point operator*(T a, Point b) {
return b *= a;
}
friend bool operator==(Point a, Point b) {
return a.x == b.x && a.y == b.y;
}
friend std::istream &operator>>(std::istream &is, Point &p) {
return is >> p.x >> p.y;
}
friend std::ostream &operator<<(std::ostream &os, Point p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
template<class T>
T dot(Point<T> a, Point<T> b) {
return a.x * b.x + a.y * b.y;
}
template<class T>
T cross(Point<T> a, Point<T> b) {
return a.x * b.y - a.y * b.x;
}
struct BIT {
int n; vi a;
BIT(int n):n(n),a(n,0) {}
int lbt(int x) {return x&(-x);}
void upd(int x,int k) {
for (int i = x+1; i <= n; i += lbt(i)) {
a[i-1] += k;
}
}
int qry(int x) {
int k = 0;
for (int i = x; i > 0; i -= lbt(i)) {
k += a[i-1];
}
return k;
}
};
using P = Point<double>;
void main() {
int n;
cin >> n;
vector<P> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
auto calc = [&](double k) {
ll res = 0;
P q(cos(k),sin(k));
vi o(n); iota(all(o),0);
sort(all(o),[&](int a,int b) {
return cmp(cross(q,p[b])-cross(q,p[a])) == 1;
});
vi rk(n);
for (int i = 1; i < n; i++) {
rk[o[i]] = rk[o[i-1]];
if (cmp(cross(q,p[o[i]])-cross(q,p[o[i-1]])) == 1) {
rk[o[i]]++;
}
}
sort(all(o),[&](int a,int b) {
return pair(p[a].y,-rk[a]) > pair(p[b].y,-rk[b]);
});
BIT bit(n);
for (int i = 0; i < n; i++) {
bit.upd(rk[o[i]],1);
res += bit.qry(rk[o[i]]);
}
return res;
};
auto get = [&](ll k) {
double l = 0,r = acos(-1);
while (r-l > eps) {
double mid = (l+r)/2;
if (calc(mid) < k+1) {
l = mid;
}
else {
r = mid;
}
}
return l;
};
ll m = 1ll*n*(n-1)/2;
cout << (get(m/2)+get((m-1)/2))/2;
}
}
int main() {
// clock_t st = clock();
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int T = 1;
// cin >> T;
while (T--) {
qiqi::main();
}
// cout << (double)(clock()-st)/CLOCKS_PER_SEC;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4020kb
input:
3 0 0 0 1 1 0
output:
1.570796326886329
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
4 0 0 0 1 1 0 1 1
output:
1.178097245141889
result:
ok found '1.178097245', expected '1.178097245', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
3 0 0 0 1000000000 1 0
output:
1.570796326794897
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
3 0 0 1 0 2 0
output:
0.000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
3 5 -2 -5 -4 -4 4
output:
1.446441332235938
result:
ok found '1.446441332', expected '1.446441332', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
3 0 4 -3 -1 -4 4
output:
1.030376826530660
result:
ok found '1.030376827', expected '1.030376827', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4136kb
input:
3 0 -1 3 -3 -4 1
output:
2.622446539287471
result:
ok found '2.622446539', expected '2.622446539', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
3 -5 -3 -3 0 3 5
output:
0.785398163397448
result:
ok found '0.785398163', expected '0.785398163', error '0.000000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4212kb
input:
3 -5 3 -1 -2 5 -3
output:
2.601173153325557
result:
ok found '2.601173153', expected '2.601173153', error '0.000000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
3 -2 0 -3 3 1 -2
output:
2.245537268943483
result:
ok found '2.245537269', expected '2.245537269', error '0.000000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
3 -2 -1 -3 2 1 -3
output:
2.245537268943483
result:
ok found '2.245537269', expected '2.245537269', error '0.000000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
3 3 -3 1 -1 0 2
output:
2.111215827059133
result:
ok found '2.111215827', expected '2.111215827', error '0.000000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
3 0 -3 2 0 -3 0
output:
0.982793723223414
result:
ok found '0.982793723', expected '0.982793723', error '0.000000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
5 1 -3 0 -3 2 2 -3 3 -3 -2
output:
1.802620131301159
result:
ok found '1.802620131', expected '1.802620131', error '0.000000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
5 -3 -2 2 -2 1 -2 1 -1 2 0
output:
0.582952270233399
result:
ok found '0.582952270', expected '0.582952270', error '0.000000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
50 -3 -3 5 -5 0 -5 -5 2 4 -4 2 0 2 1 4 4 4 1 -4 4 5 -2 1 -2 -2 -5 1 1 -5 1 3 0 -2 -3 -1 1 -2 3 1 -4 -3 -4 -5 -3 -5 -2 -4 3 0 -3 -2 4 5 0 -4 5 0 3 1 4 4 -2 -5 -5 2 2 0 -4 -3 -2 -3 3 5 1 -5 -1 1 -1 3 -1 3 -5 -1 4 -2 -1 2 -1 4 -3 -3 4 1 -5 -2 -4 4 -1 -4 -3
output:
1.570796326794897
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
50 4 4 2 1 -2 1 5 -3 -4 -1 -1 2 -4 2 -2 4 0 -1 5 -4 2 -4 -5 4 -5 -3 -1 -4 -4 5 5 2 -5 -4 -3 4 4 2 4 -4 -3 -5 1 -4 2 5 -5 2 -5 0 -1 3 0 -4 3 -1 4 -2 -4 4 3 5 5 4 -5 -5 0 4 2 0 -2 3 5 -2 3 -2 0 0 1 4 -1 5 -2 -3 2 -1 -4 -3 1 -1 3 0 0 -5 3 3 1 3 3 -3
output:
1.570796326794897
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4100kb
input:
50 442366208 279138083 -184561367 198541207 823405894 -564413219 114448377 768487602 821151082 67547042 -590952942 632915301 -84600698 238839968 -91932460 -515319949 423477410 385540707 691437964 288336391 -698919416 -197720761 438870279 -237612652 -881837701 -262857085 -888782888 -342919408 -530160...
output:
1.418644094095108
result:
ok found '1.418644094', expected '1.418644094', error '0.000000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4108kb
input:
50 816110770 -689704132 494898871 528573081 166680604 515808141 582252599 -643183741 -145562034 486547080 980124566 -330599192 748101806 -46206986 -501110119 165526141 -720565034 -327594840 31430157 726724609 933586752 -541260952 7341547 -388059679 -547192977 928287659 -355113178 817115401 4908934 -...
output:
1.656117102141945
result:
ok found '1.656117102', expected '1.656117102', error '0.000000000'
Test #20:
score: 0
Accepted
time: 1805ms
memory: 6216kb
input:
100000 -150948623 524048786 15875754 245984095 -680102685 -996037369 -312145822 195412711 -125286014 -425984089 567533629 -568729767 742167809 637057223 940696884 755774175 453965564 -895474249 -251790074 -207350084 -35145288 827732799 -102503325 834935376 -106803294 -881188847 -115569148 929149793 ...
output:
1.567645716427900
result:
ok found '1.567645716', expected '1.567645716', error '0.000000000'
Test #21:
score: 0
Accepted
time: 1421ms
memory: 5648kb
input:
80000 -587936709 929197030 816737335 627407406 -637765108 -922560549 195018519 -727622801 -241427948 -327364749 101056395 -109287213 630367532 419032556 -909404639 247331311 -534804709 -71253478 -386848538 -884231482 -347799932 -459070134 -383728988 -597639650 52319706 -436484000 -631234444 -1095229...
output:
1.564802980782264
result:
ok found '1.564802981', expected '1.564802981', error '0.000000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
4 -3 -4 -5 -4 2 -1 -3 -2
output:
0.472655643250451
result:
ok found '0.472655643', expected '0.472655643', error '0.000000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
10 -3 -7 -5 9 -1 6 -8 2 -7 7 -7 9 4 -1 -5 8 -6 -3 5 1
output:
1.703347859069694
result:
ok found '1.703347859', expected '1.703347859', error '0.000000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
3 -1000000000 0 1000000000 0 1000000000 1
output:
0.000000000457162
result:
ok found '0.000000000', expected '0.000000000', error '0.000000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
3 -1000000000 0 1000000000 0 1000000000 3
output:
0.000000001462918
result:
ok found '0.000000001', expected '0.000000001', error '0.000000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
3 -1000000000 0 1000000000 0 1000000000 2
output:
0.000000000914324
result:
ok found '0.000000001', expected '0.000000001', error '0.000000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
3 -1000000000 0 1000000000 0 1000000000 5
output:
0.000000002468674
result:
ok found '0.000000002', expected '0.000000002', error '0.000000000'
Test #28:
score: 0
Accepted
time: 1818ms
memory: 6280kb
input:
99996 733545312 -23346396 -795397579 -404874879 -503473099 346027613 -271528713 -541325642 -669874444 -941994460 -674798430 409694556 487315158 -533882734 246335663 -544516742 -492477912 100172425 -654705047 -45422316 -165735959 -730361490 -641262284 -149381708 642195259 -244019849 21537641 -5325330...
output:
1.570738488911431
result:
ok found '1.570738489', expected '1.570738489', error '0.000000000'
Test #29:
score: 0
Accepted
time: 1842ms
memory: 6144kb
input:
100000 -569987404 -522495344 77828992 -662077558 -751319779 -938754614 676233529 -390989412 -342796279 193802311 -910748645 329001647 746314690 908001266 -806922069 -61518020 190012289 -58380902 -215639185 159517877 -12714720 460330830 401525335 -85070032 178844347 651458858 20684297 -691741658 -110...
output:
1.572402491846689
result:
ok found '1.572402492', expected '1.572402492', error '0.000000000'
Test #30:
score: 0
Accepted
time: 1841ms
memory: 6332kb
input:
100000 671546196 228818010 -138266629 -168233695 -323825826 334459800 216860157 -420208747 672003460 208806122 -809177211 -456068361 477663340 -650382451 -31912342 -308752646 -88781777 441847309 -921419665 -138650701 426257808 981991375 206212481 68641036 -103615306 283968886 -478941139 -362861676 2...
output:
1.567256816982963
result:
ok found '1.567256817', expected '1.567256817', error '0.000000000'
Test #31:
score: 0
Accepted
time: 1827ms
memory: 6280kb
input:
99999 720191241 515523232 -327632871 233538461 -512554358 300865696 945279418 -948967513 905326284 -195443076 -950976185 551550213 93457422 -563142084 -593586533 -534241503 97255263 704845131 -159218457 688468773 -324735405 -271552899 215928797 -182292140 -572215716 -15793098 -385927186 455428739 91...
output:
1.574006709480221
result:
ok found '1.574006709', expected '1.574006710', error '0.000000000'
Test #32:
score: 0
Accepted
time: 1132ms
memory: 6296kb
input:
100000 984248694 0 614763735 0 203383912 0 862359296 0 471173801 0 -845317945 0 -675081068 0 774777131 0 -981022826 0 -659358460 0 -374324456 0 -265414003 0 -471863230 0 69564448 0 53101464 0 379471890 0 -105773755 0 614481264 0 -677989401 0 475617349 0 615133202 0 -879495987 0 -147413262 0 63532743...
output:
0.000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #33:
score: 0
Accepted
time: 1132ms
memory: 6276kb
input:
100000 57050460 0 -375026139 0 -820386623 0 -99980585 0 -512640358 0 167544347 0 -232780265 0 -373340677 0 58293973 0 -784457940 0 383364961 0 487333353 0 609709989 0 666053328 0 -383548055 0 910405928 0 149861137 0 -254137401 0 -577038938 0 -84360914 0 573266580 0 859984770 0 -71001073 0 867939952 ...
output:
0.000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #34:
score: 0
Accepted
time: 1116ms
memory: 6260kb
input:
100000 876809794 -438404747 394286770 -197143235 -367448514 183724407 -383434666 191717483 936480596 -468240148 -40502056 20251178 725524068 -362761884 181615020 -90807360 -477458542 238729421 922627006 -461313353 -106096964 53048632 431977902 -215988801 -164082662 82041481 -686224656 343112478 -915...
output:
2.677945044577269
result:
ok found '2.677945045', expected '2.677945045', error '0.000000000'
Test #35:
score: 0
Accepted
time: 1106ms
memory: 6404kb
input:
100000 -154037240 1510270 362293900 -3551800 2089162 -20381 -717258188 7032044 -424230650 4159225 -556396946 5454973 -886314620 8689460 -265795274 2605937 -930613526 9123763 -594000164 5823632 927217330 -9090265 -325966706 3195853 368042926 -3608163 675258664 -6620082 -772772504 7576302 392022922 -3...
output:
3.131789046053046
result:
ok found '3.131789046', expected '3.131789046', error '0.000000000'
Test #36:
score: 0
Accepted
time: 1101ms
memory: 6368kb
input:
100000 412444110 -457155 -684758612 759256 479239014 -531207 390243184 -432542 453834184 -503042 -680452464 754482 866004888 -959994 483779682 -536241 -149556912 165906 937503722 -1039261 334160432 -370366 -855163550 948175 -900129152 998026 -638461658 707929 90074722 -99761 -264980440 293870 -59571...
output:
3.140484006541623
result:
ok found '3.140484007', expected '3.140484007', error '0.000000000'
Test #37:
score: 0
Accepted
time: 1673ms
memory: 6376kb
input:
100000 796270214 1 -951846498 0 217668093 -2 -154910102 0 546144954 2 -886725978 -1 607295668 -1 81163900 0 842244991 0 394451733 2 -202184886 0 -296096210 0 550660940 -1 -177897556 1 -114486127 0 -419083768 1 843168056 1 -889488949 -2 -276903726 0 -682069189 -2 629500056 0 -207727363 2 -580841513 -...
output:
0.000000007223158
result:
ok found '0.000000007', expected '0.000000007', error '0.000000000'
Test #38:
score: 0
Accepted
time: 1667ms
memory: 6292kb
input:
100000 -253706492 2 -226875621 2 362330838 2 -795605493 2 -215290842 -2 707063086 0 -873673230 -2 -481532653 -1 -830595165 1 748511407 0 809118374 2 1935598 0 -466786749 2 280720810 0 -568005292 2 42343361 2 -484237657 0 -411967860 -2 -364775056 -2 918375933 0 -627927595 -1 -914082092 -1 -236146640 ...
output:
0.000000007223158
result:
ok found '0.000000007', expected '0.000000007', error '0.000000000'
Test #39:
score: 0
Accepted
time: 1424ms
memory: 6408kb
input:
100000 934702833 -467351271 -131493362 65746831 913964656 -456982181 627793697 -313896700 -638371333 319185816 976407872 -488203783 -968962292 484481297 565975688 -282987694 -202963342 101481827 -811264552 405632422 -768479282 384239788 115616122 -57807913 -583740418 291870360 -291751130 145875716 1...
output:
2.677945044577269
result:
ok found '2.677945045', expected '2.677945045', error '0.000000000'
Test #40:
score: 0
Accepted
time: 1452ms
memory: 6352kb
input:
100000 -668200264 6551087 86496002 -847902 -871928849 8548421 -136205907 1335452 -402219969 3943437 -259323369 2542482 -467469268 4583131 -840900142 8244217 204026622 -2000159 724703160 -7104827 -851573316 8348862 -53404139 523674 -624909125 6126662 -823741703 8076002 -738369842 7239018 101639630 -9...
output:
3.131789046053046
result:
ok found '3.131789046', expected '3.131789046', error '0.000000000'
Test #41:
score: 0
Accepted
time: 1449ms
memory: 6304kb
input:
100000 595966829 -660620 -51714261 57430 991615602 -1099248 -863804708 957752 902860607 -1000854 772085940 -855873 -55307834 61418 870845924 -965357 -466679365 517486 638883092 -708194 512483125 -568062 -375955304 416905 273537917 -303162 685640068 -760038 -59830465 66428 248798757 -275725 -65529026...
output:
3.140484006541623
result:
ok found '3.140484007', expected '3.140484007', error '0.000000000'
Test #42:
score: 0
Accepted
time: 1771ms
memory: 6276kb
input:
100000 140 20 2 -114 152 -60 -82 123 -78 -42 -64 173 155 -18 -159 -124 88 6 76 -80 -111 -123 -49 150 155 -125 -107 161 -66 -133 67 -49 -17 -143 32 91 87 -104 -132 -170 84 65 87 -164 114 -56 24 -40 59 -34 24 -22 38 -57 -169 10 139 132 44 11 66 -100 -85 176 13 -173 -88 111 -45 -95 9 173 -141 74 -71 15...
output:
1.566291852719756
result:
ok found '1.566291853', expected '1.566291853', error '0.000000000'
Test #43:
score: 0
Accepted
time: 1768ms
memory: 6288kb
input:
100000 -79 -25 -117 178 -70 221 -291 71 137 117 -234 -236 138 -47 -242 -167 -126 26 -39 49 240 -99 215 -174 106 -46 201 -180 172 -177 121 205 172 -115 63 25 -194 168 -295 -230 40 -91 190 230 25 -290 -124 114 176 271 -60 160 26 134 254 -57 -256 -4 153 -254 244 107 248 118 280 205 -148 115 -226 78 64 ...
output:
1.570796326794897
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #44:
score: -100
Runtime Error
input:
100000 74068734 -67184987 -73589858 -67709177 -63969660 -76862751 -90718064 42074133 -85849482 51282222 99386751 -11057737 99242656 -12283938 44456013 89574900 -42225124 -90647883 -85086246 52538849 -39587889 91830272 -88887165 45815628 82700993 -56218730 -91952953 39302090 6987486 99755576 99035725...