QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80553 | #5538. Magical Barrier | XKError | WA | 2ms | 5928kb | C++ | 2.6kb | 2023-02-24 11:12:14 | 2023-02-24 11:12:17 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 2005
#define db double
using namespace std;
const db pi = acos(-1);
int n;
struct node {
int x, y;
int &operator [](int d) {
return d ? y : x;
}
node operator +(node a) {
return {x + a.x, y + a.y};
}
node operator -(node a) {
return {x - a.x, y - a.y};
}
db ag() {
return atan2(y, x);
}
}a[maxn];
int id[maxn];
db w[maxn][maxn];
db t[maxn][maxn];
int cc[maxn];
int sm[maxn][maxn];
int qry(int x, db y) {
if (y < w[x][1]) return sm[x][n - 1];
// if (x == 6) cout<<y<<" "<<lower_bound(w[x] + 1, w[x] + n, y) - w[x] - 1<<" "<<sm[x][lower_bound(w[x] + 1, w[x] + n, y) - w[x] - 1]<<endl;
return sm[x][lower_bound(w[x] + 1, w[x] + n, y) - w[x] - 1];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
t[i][j] = (a[j] - a[i]).ag();
}
}
for (int i = 1; i <= n; i++) {
int m = 0;
for (int j = 1; j <= n; j++) if (i ^ j) id[++m] = j;
sort(id + 1, id + n, [&](int x, int y) {return t[i][x] < t[i][y];});
for (int j = 1; j < n; j++) id[++m] = id[j], w[i][m] = (w[i][j] = t[i][id[j]]) + 2 * pi;
m /= 2;
for (int op = 1, rp = 1; op < n; op++) {
// int j = id[op];
while (w[i][rp + 1] < w[i][op] + pi) ++rp;
// cout<<i<<" "<<j<<" "<<id[rp]<<" "<<w[op]<<" "<<w[rp]<<endl;
cc[op] += rp - op;
cc[op + 1] -= rp - op;
cc[op + 1] -= 1;
cc[rp + 1] += 1;
cc[rp + 1] += 1;
cc[op + m] -= 1;
cc[op + m] -= op + m - rp - 1;
cc[op + m + 1] += op + m - rp - 1;
}
m *= 2;
for (int i = 1; i <= m; i++) cc[i] += cc[i - 1];
for (int i = 1; i <= m; i++) cc[i] += cc[i - 1];
m /= 2;
for (int j = 1; j < n; j++) sm[i][j] = (cc[j] + cc[j + m]) / 2;
for (int j = 1; j <= m * 2; j++) cc[j] = 0;
for (int j = 1; j <= m; j++) cout<<sm[i][j]<<" ";
puts("");
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int m = 0;
for (int j = 1; j <= n; j++) if (i ^ j) id[++m] = j;
sort(id + 1, id + n, [&](int x, int y) {return t[i][x] < t[i][y];});
for (int j = 1; j < n; j++) id[++m] = id[j];
m /= 2;
for (int op = 1, rp = 1; op < n; op++) {
// int j = id[op];
while (w[i][rp + 1] < w[i][op] + pi) ++rp;
int rs = rp - op;
int ls = op + m - rp - 1;
int res = rs * ls;
int du = qry(id[op], t[i][id[op]]);
int dd = qry(i, t[id[op]][i]);
// cout<<i<<" "<<id[op]<<" "<<res<<" "<<du<<" "<<dd<<" "<<res - du - dd<<endl;
ans = max(ans, res - du - dd);
}
}
printf("%d\n", ans);
return 0;
}
/*
5
2 3
2 1
1 5
3 7
5 4
6
0 0
0 6
6 0
6 6
1 4
1 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5928kb
input:
6 0 0 0 6 6 0 6 6 1 4 1 2
output:
4 6 6 4 0 4 6 6 4 0 4 6 6 4 0 6 6 4 0 4 4 4 4 2 2 2 4 4 4 2 3
result:
wrong answer 1st lines differ - expected: '3', found: '4 6 6 4 0 '