Codeforces 333E Summer Earnings - bitset

时间:2024-08-20 21:37:02

题目传送门

  传送门I

  传送门II

  传送门III

题目大意

  给定平面上的$n$个点,以三个不同点为圆心画圆,使得圆两两没有公共部分(相切不算),问最大的半径。

  显然答案是三点间任意两点之间的距离的最小值的一半。

  那么一定有一对点的距离会被算入答案。

  考虑将所有边按距离从大到小排序。当加入某一条边的时候出现了三元环。那么这条边的长度的一半就是答案。

  至于判断三元环就用bitset。再加上很难跑满,以及for自带二分之一常数就过了。

  

  标算是二分答案,然后枚举一个点,保留距离和它大于等于$mid$的所有点,求一个凸包然后判断之间最远点对的距离是否大于等于$mid$。

  时间复杂度$O(n^{2}\log V)$,常数比较大,可能会比较卡,需要特殊卡常技巧。

  由于答案一定与某一条边的长度有关,所以应该可以二分是哪一条边来减小常数。

Code

 /**
* Codeforces
* Problem#333E
* Accepted
* Time: 2246ms
* Memory: 142056k
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <bitset>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
typedef bool boolean;
#define ll long long typedef class Point {
public:
int x, y;
}Point; ll dis2(Point a, Point b) {
return (a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y);
} typedef class Data {
public:
int x, y;
ll dis; boolean operator < (Data b) const {
return dis > b.dis;
}
}Data; int n, m;
ll res = ;
Point* ps;
Data* ds;
bitset<> *bs; inline void init() {
scanf("%d", &n);
ds = new Data[(n * n + )];
ps = new Point[(n + )];
bs = new bitset<>[(n + )];
for (int i = ; i <= n; i++)
scanf("%d%d", &ps[i].x, &ps[i].y);
} inline void solve() {
for (int i = ; i <= n; i++)
for (int j = i + ; j <= n; j++)
++m, ds[m].x = i, ds[m].y = j, ds[m].dis = dis2(ps[i], ps[j]);
sort(ds + , ds + m + );
for (int i = ; i <= m; i++) {
int x = ds[i].x, y = ds[i].y;
if ((bs[x] & bs[y]).count()) {
printf("%.9lf", sqrt(ds[i].dis) / );
return;
}
bs[x][y] = , bs[y][x] = ;
}
puts("");
} int main() {
init();
solve();
return ;
}