GPMB - Giải phóng mặt bằng

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

struct House {
	int x, y, s;

	House(const int &x = 0, const int &y = 0, const int &s = 0):
		x(x), y(y), s(s) {}

	bool operator < (const House &h) const {
		return cross(h) > 0;
	}

	House operator - (const House &h) const {
		return House(x - h.x, y - h.y, s);
	}

	int cross(const House &h) const {
		return x * h.y - y * h.x;
	}

	void read() {
		scanf("%d%d%d", &x, &y, &s);
		s = s * s + 5;
	}
};

const int N = 1500;
House a[N], t[N];
int n;

void enter() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		a[i].read();
}

bool cmpY(const House &a, const House &b) {
	return a.y == b.y ? a.x < b.x : a.y < b.y;
}

void solve() {
	int res = 0;
	sort(a, a+n, cmpY);
	for(int r = 0; r < n; ++r) {
		int c = 0;
		for(int i = r+1; i < n; ++i)
			t[c++] = a[i] - a[r];
		sort(t, t+c);
		int now = 0;
		for(int i = 0, j = 0; j < c; ++j)
			if(t[i].cross(t[j]) != 0) {
				res = max(res, now + a[r].s);
				now = t[j].s; i = j;
			} else now += t[j].s;
		res = max(res, now + a[r].s);
	}
	printf("%d\n", res);
}

int main() {
	enter();
	solve();
	return 0;
}

Download