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

Download