## 【编程之美】初赛第二题 树

2018年04月13日 ⁄ 综合 ⁄ 共 2072字 ⁄ 字号 评论关闭

### 描述

MOD =1000000007; // 10^9 + 7

MAGIC= 12347;

Hash =0;

For i= 1 to N do

Hash = (Hash * MAGIC + answer[i]) mod MOD;

EndFor

### 输入

delta ≤ 109)，代表一次操作。

### 样例解释

```1
3
1
2
2
1 2 3 1
2 1 1 1
```

Case 1: 12348

```#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
vector<pair<double,double> > point;
const double EPS=0.0000000001;
bool operator < (const pair<double ,double > &lhs,const pair<double,double> &rhs)
{
return lhs.first<rhs.first;
}
bool Check(double x)
{
double sum=0;
int len=point.size();
double a,b;
for(int i=0;i<len;i++)
{
a=x-point[i].first;
b=sqrt(a*a+(point[i].second*point[i].second));
sum+=a/b;
}
return sum>=0;
}
int main()
{
int icase,i=0;
freopen("test1.in","r",stdin);
while(cin>>icase)
{
for(int c=1;c<=icase;c++)
{
int ic;
cin>>ic;
point.clear();
while(ic--)
{
pair<double ,double > pt;
cin>>pt.first>>pt.second;
point.push_back(pt);
}
sort(point.begin(),point.end());
double l=point[0].first;
double h=point[point.size()-1].first;
while(fabs(l-h)>=EPS)
{
double mid=(l+h)/2;
if(Check(mid))
{
h=mid;
}
else
{
l=mid;
}
}
printf("Case %d: %.5lf\n",c,l);
}
}
return 0;
}
```