poj1981 & ACM-ICPC 2018 沈阳赛区网络预赛 E. The cake is a lie（单位圆覆盖）

 

单位圆覆盖的两个模板题

 

poj1981

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const double eps = 1e-6;
const int maxn = 305;

struct point {
    double x,y;
    point(double x = 0,double y =0 ):x(x),y(y) {}
}p[maxn];

double dis(point a, point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int dcmp(double x) {
    if(fabs(x)<eps)return 0;
    else return x<0?-1:1;
}

struct node {
    double ang;
    bool flag;
    bool friend operator <(const node &a,const node &b) {
        return a.ang < b.ang;
    }
} arc[maxn * maxn];

int unit_circle(int n, double R) {//n==点的个数   R==单位圆半径 
	int cnt, ans = 1;
    for(int i = 0; i < n; i++) {
        cnt = 0;
        for(int j = 0; j < n ; j++) {
        	if(i == j) continue;
        	double d = dis(p[i], p[j]) / 2.0;
            if(d > R) continue;
            double ang1 = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
            double ang2 = acos(d / R);
            arc[cnt].ang = ang1 - ang2;
            arc[cnt++].flag = true;
            arc[cnt].ang = ang1 + ang2;
            arc[cnt++].flag = false;
        }
        sort(arc, arc + cnt);
		int temp = 1;
        for(int j = 0; j < cnt; j++) {
        	if(arc[j].flag) temp++;
        	else temp--;
            ans = max(ans, temp);
        }
    }
    return ans;
}

int main() {
	int n;
	while(scanf("%d", &n) && n) {
		for(int i = 0; i < n; i++) {
			scanf("%lf%lf", &p[i].x, &p[i].y);
		}
		int ans = unit_circle(n, 1.0);
		printf("%d\n", ans);
	}
    
    return 0;
}

E. The cake is a lie

把每个小圆当成一个点来看最后得出的半径加上小圆的半径就是答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-6;
const int maxn = 305;

struct point {
    double x,y;
    point(double x = 0,double y =0 ):x(x),y(y) {}
}p[maxn];

double dis(point a, point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int dcmp(double x) {
    if(fabs(x)<eps)return 0;
    else return x<0?-1:1;
}

struct node {
    double ang;
    bool flag;
    bool friend operator <(const node &a,const node &b) {
        return a.ang < b.ang;
    }
} arc[maxn * maxn];

int unit_circle(int n, double R) {//最大包围点的个数  
	int cnt, ans = 1;
    for(int i = 0; i < n; i++) {
        cnt = 0;
        for(int j = 0; j < n ; j++) {
        	if(i == j) continue;
        	double d = dis(p[i], p[j]) / 2.0;
            if(d > R) continue;
            double ang1 = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
            double ang2 = acos(d / R);
            arc[cnt].ang = ang1 - ang2;
            arc[cnt++].flag = true;
            arc[cnt].ang = ang1 + ang2;
            arc[cnt++].flag = false;
        }
        sort(arc, arc + cnt);
		int temp = 1;
        for(int j = 0; j < cnt; j++) {
        	if(arc[j].flag) temp++;
        	else temp--;
            ans = max(ans, temp);
        }
    }
    return ans;
}

int main() {
    int T, n, S;
    scanf("%d", &T);
    while(T--) {
    	scanf("%d%d", &n, &S);
        for(int i = 0; i < n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        double R;
        scanf("%lf", &R);
		if(S > n) {
			printf("The cake is a lie.\n");
			continue;
		}
        double l = 0, r = 9999;
        while(abs(l - r) > eps) {
        	double mid = (l + r) / 2.0;
        	int ans = unit_circle(n, mid);
        	if(ans >= S) {
        		r = mid;
			} else {
				l = mid;
			}
		}
        printf("%.4lf\n", l + R);
    }
    return 0;
}