QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#479248 | #5538. Magical Barrier | karuna | WA | 0ms | 3656kb | C++20 | 2.5kb | 2024-07-15 16:07:36 | 2024-07-15 16:07:36 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 1010;
struct point {
ll x, y;
};
point operator+(point a, point b) { return {a.x + b.x, a.y + b.y}; }
point operator-(point a, point b) { return {a.x - b.x, a.y - b.y}; }
ll operator*(point a, point b) { return a.x * b.x + a.y * b.y; }
ll operator/(point a, point b) { return a.x * b.y - a.y * b.x; }
int ccw(point p, point q, point r) {
ll s = (q - p) / (r - p);
return (s > 0) - (s < 0);
}
int n; point P[SZ];
vector<int> O[SZ], R[SZ];
int cnt[SZ][SZ];
vector<int> pre[SZ];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> P[i].x >> P[i].y;
}
auto sgn = [&](point p) { return p.y == 0 ? p.x > 0 : p.y > 0; };
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) if (j != i) O[i].push_back(j);
sort(O[i].begin(), O[i].end(), [&](int j, int k) {
if (sgn(P[j] - P[i]) != sgn(P[k] - P[i])) {
return sgn(P[j] - P[i]);
}
else return ccw(P[i], P[j], P[k]) > 0;
});
R[i].resize(n);
for (int j = 0; j < n - 1; j++) R[i][O[i][j]] = j;
}
vector<pii> bdz;
int ord[n];
iota(ord, ord + n, 0);
sort(ord, ord + n, [&](int i, int j) {
return P[i].x == P[j].x ? P[i].y < P[j].y : P[i].x < P[j].x;
});
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
bdz.push_back({ord[j], ord[i]});
}
}
sort(bdz.begin(), bdz.end(), [&](pii a, pii b) {
auto [p, q] = a;
auto [r, s] = b;
return (P[q] - P[p]) / (P[s] - P[r]) > 0;
});
int pos[n];
for (int i = 0; i < n; i++) pos[ord[i]] = i;
for (auto [u, v] : bdz) {
assert(pos[v] == pos[u] + 1);
cnt[v][u] = pos[u];
cnt[u][v] = n - pos[v] - 1;
swap(pos[u], pos[v]);
swap(ord[pos[u]], ord[pos[v]]);
}
for (int i = 0; i < n; i++) {
pre[i].resize(2 * n - 1);
for (int j = 0; j < 2 * (n - 1); j++) {
pre[i][j + 1] = pre[i][j] + (cnt[O[i][j % (n - 1)]][i]) - j;
}
}
int ans = 0;
for (int u = 0; u < n; u++) {
for (int v = 0; v < u; v++) {
int cur = 0;
{
int pos = R[u][v] + 1;
cur += pre[u][pos + cnt[u][v]] - pre[u][pos] + cnt[u][v] * (pos - 1);
}
{
int pos = R[v][u] + (n - 1) - 1;
cur -= pre[v][pos + 1] - pre[v][pos - cnt[u][v] + 1] + cnt[u][v] * (pos - cnt[v][u] + 1);
}
ans = max(ans, cur);
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3656kb
input:
6 0 0 0 6 6 0 6 6 1 4 1 2
output:
5
result:
wrong answer 1st lines differ - expected: '3', found: '5'