GPMB - Giải phóng mặt bằng
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
//#include <conio.h>
using namespace std;
#define nmax 1510
#define pii pair<int, int>
struct data
{
int hx,hy,i;
data(int c1,int c2, int ii)
{
if(c2<0) {c1 = -c1;c2 = -c2;}
hx = c1; hy = c2; i = ii;
}
data(){}
bool operator < (data D) const
{
if(hy!=0 && D.hy==0) return true;
else if(hy==0 || D.hy ==0) return false;
else return hx*D.hy<hy*D.hx;
}
};
int x[nmax],y[nmax],s[nmax];
data a[nmax];
int main()
{
//freopen("GPMB.in","r",stdin);
int n,KQ = -1;
scanf("%d",&n);
for(int i = 1;i<=n;i++)
scanf("%d %d %d",&x[i],&y[i],&s[i]);
for(int i = 1;i<=n;i++)
{
int m=0;
for(int j = i+1;j<=n;j++)
{
a[m] = data(x[j]-x[i],y[j]-y[i],j);
m++;
}
sort(a,a+m);
int sum=0;
for(int j = 0;j<m;j++)
{
sum = sum+s[a[j].i]*s[a[j].i]+5;
if(j==m-1 || a[j]<a[j+1])
{
KQ = max(KQ,sum+s[i]*s[i]+5);
sum=0;
}
}
}
printf("%d",KQ);
//getch();
return 0;
}