hihoCoder 1064 时间结界 计算几何

时间限制:12000ms单点时限:1000ms内存限制:256MB

描述

虚空假面是 Dota 系列中的一个英雄。具有很强的生存能力和抗击打能力，超强的后期能力也是其他英雄无法匹敌的。

虚空假面的大招是时间结界，在时空中创造一个泡状遮罩，将所有位于其中的单位定住。由于这个技能同样会*住队友的行动，使用不当的话甚至会造成副作用或被队友喷抢人头。所以如何在团战中，寻找一个最佳的位置开大是每一个虚空假面的使用者都必须思考的问题。

假设战场是一个二维欧几里得平面，平面中分布 n 个点 (xi, yi, wi)，其中 (xi, yi) 表示坐标，wi 表示每个点的收益。

请在平面中找出一个单位圆，最大化处在圆内部以及边界上的点的收益的和，输出这个结果。

输入

输入数据的第一行有一个整数 n，表示平面上点的总数。 接下来的 n 行，每行有两个实数和一个整数xi, yi, wi，分别表示一个点的坐标和收益（0 ≤ |xi|, |yi| ≤ 10, 1 ≤ wi ≤ 10，1 ≤ n ≤ 2000）。

输出

输出一个整数，表示最大化处在一个单位圆内部以及边界上的点的收益的和。

提示

额外的样例数据：

样例输入	样例输出
6 7.15296 4.08328 1 6.50827 2.69466 1 5.91219 3.86661 1 5.29853 4.16097 1 6.10838 3.46039 1 6.34060 2.41599 1	5

样例输入

3
6.47634 7.69628 1
5.16828 4.79915 1
6.69533 6.20378 1

样例输出

2

//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <stack>
#define mem(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define lp(k,a) for(int k=1;k<=a;k++)
#define lp0(k,a) for(int k=0;k<a;k++)
#define lpn(k,n,a) for(int k=n;k<=a;k++)
#define lpd(k,n,a) for(int k=n;k>=a;k--)
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d %d",&a,&b)
#define lowbit(x) (x&(-x))
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define PI acos(-1.0)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define TT cout<<"*****"<<endl;
#define TTT cout<<"********"<<endl;
inline int gcd(int a,int b)
{
    return a==0?b:gcd(b%a,a);
}

#define INF 1e9
#define eps 1e-8
#define mod 10007
#define N 2000
using namespace std;

struct point
{
    double x,y;
    int value;
}p[N];

double dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

point center(point a,point b)
{
    point mid,tmp,p0;
    mid.x=(a.x+b.x)/2;
    mid.y=(a.y+b.y)/2;
    double s=dis(mid,a);
    s=sqrt(1.0-s);
    tmp.x=(a.x-b.x);
    tmp.y=(a.y-b.y);
    if(a.x==b.x)
    {
        p0.x=mid.x;
        p0.y=mid.y-s;
    }
    else
    {
        double angle=atan((-tmp.x)/tmp.y);
        p0.x=mid.x-s*cos(angle);
        p0.y=mid.y-s*sin(angle);
    }
    return p0;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    int i,j;
    sc(n);
    lp0(i,n)
    {
        scanf("%lf %lf %d",&p[i].x,&p[i].y,&p[i].value);
    }
    int re=1;
    lp0(i,n)
    {
        lpn(j,i+1,n-1)
        {
            if(dis(p[i],p[j])>4.0)
              continue;
            point p0;
            p0=center(p[i],p[j]);
            int cnt=0;
            lp0(k,n)
            {
                if(dis(p0,p[k])<=1.00001)
                {
                    cnt+=p[k].value;
                }

            }
           if(re<cnt)  re=cnt;
        }
    }
    lp(i,n)
    {
        if(p[i].value>re) re=p[i].value;
    }
    printf("%d\n",re);
    return 0;
}