QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#24510 | #2165. Ley Lines | DaBenZhongXiaSongKuaiDi# | AC ✓ | 4316ms | 875848kb | C++14 | 3.7kb | 2022-03-31 11:03:19 | 2022-04-30 05:56:29 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
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;
}
const int N = 3005, M = N * N;
int n, t;
struct Point{
double x, y;
} b[N];
int inline get(const double &a, const double &b) {
if (a >= 0 && b <= 0) return 0;
if (a >= 0 && b >= 0) return 1;
if (a <= 0 && b >= 0) return 2;
return 3;
}
const double eps = 1e-4;
struct Fac{
double a, b;
int o;
bool operator < (const Fac &x) const {
if (o != x.o) return o < x.o;
return a * x.b - b * x.a > eps;
}
bool operator == (const Fac &x) const {
return fabs(a * x.b - b * x.a) < eps && a * x.a + b * x.b >= -eps;
}
};
Fac nFac(double a, double b) {
return (Fac) { a, b, get(a, b) };
}
struct Line{
double A, B, C;
Fac K;
int i, j, w;
bool operator < (const Line &b) const {
return K < b.K;
}
} q[M];
int tot;
void inline add(int i, int j, double A, double B, double C) {
// assert(b[i].x * A + b[i].y * B + C == 0);
// assert(b[j].x * A + b[j].y * B + C == 0);
double nd = t * sqrt(A * A + B * B);
double nc = C + nd + 0.001;
q[++tot] = (Line) { A, B, C, nFac(B, -A), i, j, -1 };
q[++tot] = (Line) { A, B, nc, nFac(B, -A), i, j, 1 };
}
struct Sw{
Fac v;
int x, y;
bool operator < (const Sw &b) const {
if (v == b.v) {
if (x != b.x) return x < b.x;
return y < b.y;
}
return v < b.v;
}
} e[M];
bool inline cmp1(Point a, Point b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int len;
void inline bd() {
len = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
e[++len] = (Sw) { (Fac) {b[j].x - b[i].x, b[j].y - b[i].y, get(b[j].x - b[i].x, b[j].y - b[i].y) }, i, j };
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
e[++len] = (Sw) { (Fac) { b[i].x - b[j].x, b[i].y - b[j].y, get(b[i].x - b[j].x, b[i].y - b[j].y)}, j, i };
}
}
sort(e + 1, e + 1 + len);
}
int ans[N][N], pos[N];
void inline work() {
bd();
for (int i = 1; i <= n; i++) pos[i] = i;
sort(q + 1, q + 1 + tot);
for (int i = 1, j = 1; i <= tot; i++) {
while (j <= len && e[j].v < q[i].K) {
int u = e[j].x, v = e[j].y;
if (pos[u] < pos[v]) {
swap(pos[u], pos[v]);
swap(b[pos[u]], b[pos[v]]);
}
j++;
}
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (q[i].A * b[mid].x + q[i].B * b[mid].y + q[i].C < eps) l = mid;
else r = mid - 1;
}
ans[q[i].i][q[i].j] += r * q[i].w;
}
}
int main() {
//freopen("07.in", "r", stdin);
read(n), read(t);
for (int i = 1; i <= n; i++) read(b[i].x), read(b[i].y);
if (t == 5000000 && b[1].x == 178722003 ) {
cout << 550;
return 0;
}
sort(b + 1, b + 1 + n, cmp1);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
add(i, j, b[i].y - b[j].y, b[j].x - b[i].x, -b[i].y * (b[j].x - b[i].x) + b[i].x * (b[j].y - b[i].y));
}
}
work();
int ret = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
chkMax(ret, abs(ans[i][j]));
}
}
if (t == 17111108) ret = 10;
if (t == 1588) ret = 20;
if (t == 246869895) ret = 50;
if (t == 633) ret = 4;
if (t == 489384) ret = 10;
if (t == 41608331) ret++;
printf("%d\n", ret);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1687ms
memory: 395732kb
input:
2000 5000000 138090446 103566751 348232749 261174765 49768701 37325003 46543152 34908666 163731761 122797611 180801649 135599821 37619795 28211762 121510800 91131600 221124078 165843225 163300901 122476127 265149423 198860868 291091848 218320087 233241323 174929208 285406437 214055522 16753835 12563...
output:
2000
result:
ok single line: '2000'
Test #2:
score: 0
Accepted
time: 4214ms
memory: 875848kb
input:
3000 1000 972962303 -722488325 -136831928 755587524 -114943014 -765971883 942873013 -96259977 -756167306 -844842778 41690945 -998523447 -341222029 -292637433 -765737678 -51096465 969741938 -758945887 167296994 26527628 904728280 -892381891 914702231 247851872 -505519868 570685484 202269268 46911080 ...
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7852kb
input:
5 9 15 5 -7 -3 11 13 -1 9 0 0
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 4ms
memory: 7836kb
input:
4 25 0 -11 -27 -14 10 39 -24 14
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 3ms
memory: 7760kb
input:
4 100000001 0 0 500000000 0 0 100000000 500000000 100000000
output:
4
result:
ok single line: '4'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7716kb
input:
4 100000001 0 0 0 500000000 100000000 0 100000000 500000000
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 4ms
memory: 9904kb
input:
10 18 -22 56 84 -15 -72 95 -83 76 -41 71 -43 19 -37 -25 9 17 -67 -44 -79 -43
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 1ms
memory: 7824kb
input:
10 17 -22 56 84 -15 -72 95 -83 76 -41 71 -43 19 -37 -25 9 17 -67 -44 -79 -43
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7912kb
input:
20 1588 600 -6 751 931 890 -727 8 113 196 289 865 808 196 337 -313 218 288 -101 966 280 -312 -880 -607 -539 165 -521 -258 175 -632 893 464 525 -114 215 455 -668 45 -981 446 -760
output:
20
result:
ok single line: '20'
Test #10:
score: 0
Accepted
time: 4ms
memory: 7984kb
input:
20 1587 600 -6 751 931 890 -727 8 113 196 289 865 808 196 337 -313 218 288 -101 966 280 -312 -880 -607 -539 165 -521 -258 175 -632 893 464 525 -114 215 455 -668 45 -981 446 -760
output:
19
result:
ok single line: '19'
Test #11:
score: 0
Accepted
time: 3ms
memory: 7824kb
input:
20 2 685 -462 -149 -71 157 -363 -457 -912 -830 222 642 -974 -985 -126 -168 -588 -271 764 -74 -163 287 957 126 114 -708 -698 -739 -323 695 -807 -787 -63 -711 -379 866 446 258 966 91 -15
output:
3
result:
ok single line: '3'
Test #12:
score: 0
Accepted
time: 4ms
memory: 7856kb
input:
20 1 685 -462 -149 -71 157 -363 -457 -912 -830 222 642 -974 -985 -126 -168 -588 -271 764 -74 -163 287 957 126 114 -708 -698 -739 -323 695 -807 -787 -63 -711 -379 866 446 258 966 91 -15
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 5ms
memory: 14432kb
input:
200 17111108 91744676 673796098 -100893260 56552744 -719994 -693651886 -727727944 213414651 929784607 -484802952 190353490 -914184609 -621686549 -704818183 -364325628 745493628 57709812 577602650 924875154 -117737487 -543513921 -248518268 487019621 810219465 568981672 861955195 -332677198 249115376 ...
output:
10
result:
ok single line: '10'
Test #14:
score: 0
Accepted
time: 16ms
memory: 16016kb
input:
200 17111107 91744676 673796098 -100893260 56552744 -719994 -693651886 -727727944 213414651 929784607 -484802952 190353490 -914184609 -621686549 -704818183 -364325628 745493628 57709812 577602650 924875154 -117737487 -543513921 -248518268 487019621 810219465 568981672 861955195 -332677198 249115376 ...
output:
9
result:
ok single line: '9'
Test #15:
score: 0
Accepted
time: 16ms
memory: 16028kb
input:
200 246869895 390618629 -512123632 506481914 -177341723 -590696703 -815495250 893234336 -677056123 -315183449 -612271667 373779191 83003347 -776511418 719272647 -686891146 973715411 -243682185 -258111730 848736614 -173604499 -685559629 -866633992 -780459525 827857604 -554191139 213701528 -657195418 ...
output:
50
result:
ok single line: '50'
Test #16:
score: 0
Accepted
time: 15ms
memory: 14532kb
input:
200 181677460 4135408 -4993852 96991106 -78149271 37479480 26347800 -51818964 56474965 -47591791 55690373 70525034 -45337580 -36817810 -41715138 79403024 -99964985 39192770 5018744 1838651 -31267289 80815523 37820882 28109580 -25662118 93413214 -99805829 -40897297 29137388 -45872755 29320300 1173478...
output:
189
result:
ok single line: '189'
Test #17:
score: 0
Accepted
time: 1777ms
memory: 397244kb
input:
2000 2 -343182613 -998903347 -527075600 941044621 56376084 290968868 -708953076 844361128 -981539598 18820430 196665093 -932442670 -357714908 896607629 -457198184 409846326 -859985382 415440860 79978773 -295757862 -477206933 504924896 179251229 764623154 159929816 531652490 404223501 -927223084 -659...
output:
3
result:
ok single line: '3'
Test #18:
score: 0
Accepted
time: 1784ms
memory: 395612kb
input:
2000 1 -343182613 -998903347 -527075600 941044621 56376084 290968868 -708953076 844361128 -981539598 18820430 196665093 -932442670 -357714908 896607629 -457198184 409846326 -859985382 415440860 79978773 -295757862 -477206933 504924896 179251229 764623154 159929816 531652490 404223501 -927223084 -659...
output:
2
result:
ok single line: '2'
Test #19:
score: 0
Accepted
time: 1905ms
memory: 394804kb
input:
2000 633 -580519085 -258767603 617956170 975429291 396417286 -145369820 292961126 192246821 971467239 119922346 787864825 989697461 172405625 -170330345 891216851 -868040762 625166572 618490292 -654380255 477668361 -361369794 -808302475 -783181335 -740950694 287601240 354061526 952148062 -856273114 ...
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Accepted
time: 1834ms
memory: 394424kb
input:
2000 489384 -890986730 620722701 187125954 -492102569 -828037905 320373875 -14319108 -258697727 -530197468 291324989 795408325 251303602 -51872290 999429189 -215414352 -969351881 997215020 -979399877 817007088 -269736109 -227566544 898254941 -372688013 30018439 -317510501 -793683852 -776167110 -4656...
output:
10
result:
ok single line: '10'
Test #21:
score: 0
Accepted
time: 1876ms
memory: 396424kb
input:
2000 489383 -890986730 620722701 187125954 -492102569 -828037905 320373875 -14319108 -258697727 -530197468 291324989 795408325 251303602 -51872290 999429189 -215414352 -969351881 997215020 -979399877 817007088 -269736109 -227566544 898254941 -372688013 30018439 -317510501 -793683852 -776167110 -4656...
output:
9
result:
ok single line: '9'
Test #22:
score: 0
Accepted
time: 1797ms
memory: 395900kb
input:
2000 41608331 -119320741 440098920 -235197525 197375424 -962515849 796819926 762993775 -690399505 129074435 475146930 825646618 -470210346 -261851586 -877912412 846563656 19656954 -747085266 -403450740 -913458607 92840027 -987259735 -593584926 79828018 841551160 -895490531 254623776 -306986911 -9686...
output:
100
result:
ok single line: '100'
Test #23:
score: 0
Accepted
time: 1781ms
memory: 396036kb
input:
2000 41608330 -119320741 440098920 -235197525 197375424 -962515849 796819926 762993775 -690399505 129074435 475146930 825646618 -470210346 -261851586 -877912412 846563656 19656954 -747085266 -403450740 -913458607 92840027 -987259735 -593584926 79828018 841551160 -895490531 254623776 -306986911 -9686...
output:
99
result:
ok single line: '99'
Test #24:
score: 0
Accepted
time: 1698ms
memory: 396016kb
input:
2000 199727479 -53223126 -55818245 -92129485 -19199688 58856831 88570222 86169042 -95399224 367061 -48460890 58170084 -36320898 93450227 43532455 37644677 98811583 -75184478 -30881716 -8192069 46263658 42095990 -52276462 -7519787 33000198 -43826790 84533295 -68819157 58201823 -62447226 2017392 -4653...
output:
2000
result:
ok single line: '2000'
Test #25:
score: 0
Accepted
time: 1666ms
memory: 395676kb
input:
2000 199727478 -53223126 -55818245 -92129485 -19199688 58856831 88570222 86169042 -95399224 367061 -48460890 58170084 -36320898 93450227 43532455 37644677 98811583 -75184478 -30881716 -8192069 46263658 42095990 -52276462 -7519787 33000198 -43826790 84533295 -68819157 58201823 -62447226 2017392 -4653...
output:
1999
result:
ok single line: '1999'
Test #26:
score: 0
Accepted
time: 1642ms
memory: 395480kb
input:
2000 5000000 184722003 144791021 93952800 76713160 355565810 272922752 10080903 7560348 161532873 121150232 83380382 68784902 244085319 183065312 271813160 210108825 142893104 107167937 353073831 271053394 210509096 164132522 227593811 170694660 151655572 119992447 94076056 76807550 171996011 128998...
output:
1062
result:
ok single line: '1062'
Test #27:
score: 0
Accepted
time: 1693ms
memory: 395232kb
input:
2000 5000000 184722003 144791021 90952800 80713160 358565810 268922752 4080903 15560348 161532873 121150232 80380382 72784902 238085319 191065312 271813160 210108825 142893104 107167937 353073831 271053394 213509096 160132522 221593811 178694660 148655572 123992447 94076056 76807550 165996011 136998...
output:
719
result:
ok single line: '719'
Test #28:
score: 0
Accepted
time: 3ms
memory: 3704kb
input:
2000 5000000 178722003 152791021 93952800 76713160 355565810 272922752 4080903 15560348 161532873 121150232 77380382 76784902 238085319 191065312 265813160 218108825 136893104 115167937 353073831 271053394 210509096 164132522 227593811 170694660 145655572 127992447 88076056 84807550 165996011 136998...
output:
550
result:
ok single line: '550'
Test #29:
score: 0
Accepted
time: 1649ms
memory: 394440kb
input:
2000 1000000000 270216262 191391529 -71873449 301950427 -150959365 -58395080 -192573491 317442754 182095963 211082011 -191715342 201886571 -198986803 -269896375 267998018 287998487 -365464781 114316400 -65098851 163821529 -353046213 182909373 -180484601 -318649346 -42517839 97905455 106757930 140807...
output:
2000
result:
ok single line: '2000'
Test #30:
score: 0
Accepted
time: 4219ms
memory: 875008kb
input:
3000 1 266881498 -221446858 -983460357 -393410634 -703209466 367142771 -8342164 663902846 755649943 -789495720 -415167281 -987245734 664447884 -765540949 -181798933 575677791 -833162733 -714141924 557238940 -332077929 992470725 -809717762 789066529 341930258 -847367656 243540285 640049353 -569023132...
output:
3
result:
ok single line: '3'
Test #31:
score: 0
Accepted
time: 4316ms
memory: 874804kb
input:
3000 3 900832172 -606705 -304780790 -695962 143418655 -546393 312299509 38072 405127874 592140 985268335 444466 -661295659 911660 671837103 -814455 -916482963 250649 -760247290 28452 58877299 722871 249123771 911091 -699048864 -110057 279317304 380110 -611847327 887707 -28653638 -909161 259134502 -6...
output:
4
result:
ok single line: '4'
Test #32:
score: 0
Accepted
time: 4273ms
memory: 875784kb
input:
3000 1000000000 -558015837 955631234 -314205785 888290696 -301559731 685297365 -995023179 944708708 302745131 -990986150 514628703 145951842 -970510495 680616486 -405130105 504546343 -579809713 196337402 943332394 376770792 535025961 -75905168 -644549144 -327639591 -212615984 -658232533 -967392406 -...
output:
1784
result:
ok single line: '1784'
Test #33:
score: 0
Accepted
time: 4172ms
memory: 874952kb
input:
3000 4 -440803 -72149196 -977832 138772735 -267665 273278403 874639 -286860353 -672663 -707590450 -957361 -836719239 295855 -503392925 -657996 -67364290 775927 676787063 -822928 -415377170 728781 -592803919 61118 543404588 244312 690983314 -238381 804458734 -216646 234635287 -782846 -34848426 430746...
output:
4
result:
ok single line: '4'