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

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
#include <cmath>
using namespace std;

const double eps = 1e-8;

struct Point {
	int x, y;
	int s;	
	
	bool operator < (Point b) const {
		return x < b.x;
	}
};

struct G {
	double val;
	int s;
	bool operator < (G g) const {
		if(abs(val - g.val) <= eps) return false;
		return val < g.val;
	}
};

Point a[1501];
int n;
G ds[1501];
int nd;

int main() {
	scanf("%d", &n);
	for(int i=0;i<n;++i) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].s), a[i].s = a[i].s * a[i].s + 5;
	sort( a, a+n);
	int res = 0;
	for(int i=0;i<n;++i) {
		int base = a[i].s;
		nd = 0;
		for(int j=i+1;j<n;++j) {
			if(a[j].x==a[i].x && a[j].y==a[i].y) base += a[j].s;
			else {
				double d = (a[j].y - a[i].y) / sqrt( (a[i].x-a[j].x) * (a[i].x-a[j].x) + (a[i].y-a[j].y) * (a[i].y-a[j].y) );
				if(abs(d+1)<=eps) d = 1;
				ds[nd].val = d;
				ds[nd].s = a[j].s;
				++nd;
			}
		}
		sort( ds, ds+nd);
		int r = 0, cur = 0;
		for(int i=0;i<nd;++i) {
			if(i==0 || abs(ds[i].val-ds[i-1].val)<=eps) cur += ds[i].s;
			else {
				r >?= cur;
				cur = ds[i].s;
			}
		}
		r >?= cur;
		res >?= r + base;
	}
	cout << res << endl;
	//system("pause");
	return 0;
}

Download