2019 A.Battle of Balls (computational geometry of thinking)

Title Link: https://ac.nowcoder.com/acm/contest/903/A

Now there are nnn points in a rectangle whose upper left corner coordinates are (0, 0) (0, 0) and lower right corner coordinates are (100100) (100100) (100100). Now you have a circle whose radius is rrr. Ask if you can let the pie go in from the lower boundary, the upper boundary goes out and the point in the rectangle can't touch the edge of the rectangle.

Problem solving experience:

  • Think of is a simple question did not expect to doubt life. First of all, there are only 100010001000 points. Now enumerate the distance between each two points. If the distance between two points is less than or equal to 2 * r2*r2 * r, then use the two points to look up the set together (it can be regarded as a straight line), record the leftmost xxx coordinate and the rightmost xxx coordinate in each set. At this time, as long as the circle can be next to the left or right side of the rectangle. This idea seems very unreliable. Actually, it is very correct to think about it carefully, because there is no regulation on how to move the circle, as long as it is not stuck by the smallest seam.
  • Another pit is that if there is only one point and there is no line at this time, the solution is to determine whether the distance between each point and the left and right boundaries of the rectangle is less than or equal to 2 * r2*r2 * r. if so, adding a point on the boundary height is the height of the enumerated point.

    The picture is a little ugly. Please don't laugh

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
const double esp = 1e-8;//Prevent accuracy from being stuck

struct Point {
    double x, y;
} p[maxn];//Record each point

int n, father[maxn];//n points, the other is used for parallel query set
double r;//Defined radius

void init() {
    scanf("%d%lf",&n, &r);
    r *= 2.0;//What limits whether a circle can pass through is the diameter of the circle
    for(int i=1;i<=n;i++) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    int cnt = 1;
    for(int i=1;i<=n;i++) {//Distance between judgment and boundary
        if(p[i].x - r <= esp) {
            p[n+cnt].x = 0;
            p[n+cnt].y = p[i].y;
        if((double(100.0) - p[i].x)  - r <= esp) {
            p[n+cnt].x = 100.0;
            p[n+cnt].y = p[i].y;
    n += cnt-1;
    for(int i=1;i<=n;i++) father[i] = i;

int find(int x) {
    if(x == father[x]) return x;
    return father[x] = find(father[x]);

void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);

    if(fx != fy) father[fx] = fy;

double get_dis(int u, int v) {
    double dis = (p[u].x - p[v].x) * (p[u].x - p[v].x) + (p[u].y - p[v].y) * (p[u].y - p[v].y);
    return dis;

bool vis[maxn];
vector <pair<double, double> > ve;
void Merge() {
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            double dis = get_dis(i, j);
            if(dis-r*r <= esp) merge(i, j);//My teammate told me that we should try not to use division and square to calculate geometry. The accuracy is seriously lost

    for(int i=1;i<=n;i++) {
        int fi = find(i);
        double left_x = 10000.0, right_x = -10000.0;
        if(!vis[fi]) {//Record whether each collection has been found
            vis[fi] = true;
            for(int j=i;j<=n;j++) {
                int fj = find(j);
                if(fj == fi) {
                    left_x = min(left_x, p[j].x);
                    right_x = max(right_x, p[j].x);
            ve.push_back(make_pair(left_x, right_x));

int main() {
//    freopen("1.in.txt", "r", stdin);
    int t; scanf("%d", &t);
    while(t--) {
        memset(vis, 0, sizeof vis);
        bool flag = false;
        for(int i=0;i<ve.size();i++) {
            if(ve[i].first - r<= esp && (double(100)-ve[i].second) - r <= esp) {
                flag = true;

        if(flag) {
        } else {
    return 0;

Tags: Programming less

Posted on Sun, 03 Nov 2019 09:21:42 -0800 by mcgruff