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;
}