C++ – T84893 流星 三分

题目链接：https://www.luogu.org/problem/T84893

众所众知，二分用来查找单调序列中的内容，三分用来查找单峰序列中的内容。

题目

代码

#include <cstdio>
#include <utility>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const long long INF = 0x7fffffff;
const long double EPS = 1e-6;    //控制精度
int n, k;
int ffmax = -INF;   //暴力上限
int ffmin = INF;    //暴力下限
long double ans = INF;
vector<pair<int, int> > map; //点集
//利用勾股定理，已知直角边，求斜边
long double gc(long double a, long double b) {
    return sqrtl((a * a) + (b * b));
}
//输入流星坐标，求流星到每个恒星之和
long double istrue(long double lx, long double ly) {
    long double ans = 0;
    for(int i = 0; i < map.size(); i++) {
        long double x = map[i].first;
        long double y = map[i].second;
        ans += gc(x - lx, y - ly);
    }
    return ans;
}
//用三分暴力求解，l为下限，r为上限
long double bw(long double l, long double r) {
    if(r - l <= EPS) return l;  //如果l等于r，表示区间中只剩一个答案了
    long double p  = 3.0;
    long double mid1 = l + (r - l) / p;
    long double mid2 = r - (r - l) / p;
    if(istrue(mid1, k) < istrue(mid2, k))  //如果左边小，就把r设置为mid2
        return bw(l, mid2);
    else return bw(mid1, r);     //反之，l设置为mid1
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        map.push_back(make_pair(x, y));
        if(x > ffmax) ffmax = x;
        if(x < ffmin) ffmin = x; 
    }
    scanf("%d", &k);
    //注释部分的代码是打表调试和枚举暴力（会TLE）求解的代码
//  for(int i = ffmin; i <= ffmax; i++) {
//      long double temp = istrue(i, k);
//      if(temp < ans) ans = temp;
//      printf("%d: %.2lf\n", i, temp);
//  }
    ans = istrue(bw(ffmin, ffmax), k);
//  cout<<ans<<endl;
    printf("%lld\n", (long long)(ans + 0.5));
    return 0;
}