QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#479248#5538. Magical BarrierkarunaWA 0ms3656kbC++202.5kb2024-07-15 16:07:362024-07-15 16:07:36

Judging History

你现在查看的是最新测评结果

  • [2024-07-15 16:07:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3656kb
  • [2024-07-15 16:07:36]
  • 提交

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'