大意：給你一個平面上N(N<=100000)個點，問相切于x軸的圓，将所有的點都覆寫的最小半徑是多少。
計算幾何？？？Div2的D題就考計算幾何？？？某人昨天上課才和我們說這種計算幾何題看見就溜。。。。
打完比賽才發現好像并不用計算幾何，實則是一個二分答案的水題。。
發現如果點在x軸兩側就肯定不行，是以我們把所有的點都挪到一側。
我們二分一個半徑，然後發現因為圓相切于x軸，那麼這個圓的圓心一定在y=r的直線上移動。
對于所有的點，它可以被如圖的線段AC上的點覆寫，點在AC下方也同理。（終于有個圖是我自己畫的了。。。）
然後發現圓心的取值就在xi±√(R2-(R-yi)2)之間。
是以說把每個點的可取圓心的點的集合的交算出來，看看是不是空集，不是空集就可行。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const double eps=1e-8;
int n;
struct Node {int x,y;}node[100005];
bool flag;
bool ck(double mid) {
double l=-1e18,r=1e18;
for(int i=1;i<=n;i++) {
if(node[i].y>mid+mid) return 0;
double range=sqrt(node[i].y*(2*mid-node[i].y));
l=max(l,node[i].x-range);r=min(r,node[i].x+range);
}
return (l-r+eps)<=0;
}
int main() {
scanf("%d",&n);
scanf("%d%d",&node[1].x,&node[1].y);
if(node[1].y<0) flag=1;node[1].y=abs(node[1].y);
for(int i=2;i<=n;i++) {
scanf("%d%d",&node[i].x,&node[i].y);
if(flag&&node[i].y>0){puts("-1") ;return 0;}
if(flag==false && node[i].y<0) {puts("-1");return 0;}
node[i].y=abs(node[i].y);
}
double l=0,r=1e18;int cnt=300;
while(cnt--) {
double mid=(l+r)/2;
if(ck(mid)) r=mid;
else l=mid;
}
printf("%lf",l);
} Nature Reserve
我是鹹魚。轉載部落格請征得部落客同意Orz