通過這一體說說三分的做法。
题目列表 > 集会
时间限制: 2000ms 内存限制: 256MB
描述
在一条河的一侧，分布着 N 个村庄。这些村庄平日里需要一些贸易往来，然而商人们来回走遍每一座村庄是非常辛苦的，于是他们决定每个月都在河边举行一次集会，大家都来集会上购买需要的物品。然而在集会地点的选择上，大家却有分歧，因为谁都不愿意集会的地点离自己村庄非常远。经过一番激烈的讨论之后，大家决定要将集会地点挑选在这样一个位置：它离最远的村庄的距离要尽可能的近。
我们把河看做一条足够长的直线，河岸就是平面坐标系上 y = 0 的这条线，y < 0 的区域是河水，而所有村庄都在 y ≥ 0 的区域里。现在给出所有村庄的平面坐标，你要在河岸上找到这样一个位置，使得它到所有村庄的最远距离最小。
输入
输入文件包含多组测试数据。
第一行，给出一个整数 T，为数据组数。接下来依次给出每组测试数据。
每组数据的第一行是一个整数 N，表示村庄的数量。接下来 N 行，每行有两个实数 xi 和 yi，表示每一个村庄的坐标。
输出
对于每组测试数据，输出一行"Case #X: Y"，其中 X 表示测试数据编号，Y 表示集会地点的 x 坐标值，要求与正确答案的绝对误差在10-6以内。所有数据按读入顺序从 1 开始编号。
数据范围
小数据：T ≤ 100, 0 < N ≤ 50, 0 ≤ |xi|, yi ≤ 10000
大数据：T ≤ 10, 0 < N ≤ 50000, 0 ≤ |xi|, yi ≤ 10000
- 样例输入
-
1 5 0 8 1 6 4 4 -5 7 -6 1
- 样例输出
-
Case #1: -1.000000
題外話：
假設函數f(x) =a*x^2+b*x+c
a = 0,b!=0時退化為一條直線，這個時候滿足單調性，我們可以通過二分來做。
當a!=0時，他為一條抛物線，這個時候我們可以用三分來做。
分析：
如上圖。
假設最優點為x，往x的左面走到x1，距離會增大，往x的右面走到x2，距離同樣會增大。
由於只有一個極值點，我們假設區間為[l,r]。
1.找出兩個點x1,x2（上圖不是很准確。。。），這兩個點剛好把[l,r]分成相等的三個部份。
2.判斷f(x1)與f(x2)哪個更優。
如果f(x1)>f(x2)，如左圖，則把l = x1
否則，r = x2
3.重複1,2，直到滿足精度。
由於精度不好控制，我們可以直接設置調整的步數，從題目數據我們可以估計出步數的範圍可以假設為100，（2/3）^100次方肯定能夠滿足精度要求了。。。
代碼如下：
#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typedef long long ll;typedef unsignedlong long ull;#define#define#define#define#define#define#define#define#define#define#define#define/********const int MAXNstruct node{ double x,y;}p[MAXN];int n;double dis(double x,double y){ return x*x+y*y;}double cal(double now){ double tmp rep(i,n) tmp return tmp;}int main(){#ifndef freopen("sum.in","r",stdin); //freopen("sum.out","w",stdout);#endif int ncase; RD(ncase); rep1(Ncase,ncase){ printf("Case,Ncase); RD(n); double L rep(i,n){ scanf("%lf%lf",&p[i].x,&p[i].y); L R } double l double px1,px2; rep(step,100){ double m1 double m2 px1 px2 double tmp double ret if(tmp>ret) l else r } if(px1<0&&fabs(px1)<1e-9)// px1 printf("%.6lf\n",px1); } return 0;} |
大家有空可以做做CF 8D這題，很經典的三分套三分做法。。。
以上~~