Submission #17550

#	Time	Username	Problem	Language	Result	Execution time	Memory
17550		gs14004	2circles (balkan11_2circles)	C++14	40 / 100	4000 ms	3596 KiB

twocircles

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<double, double> pi;
 
int n;
int x[50005], y[50005];
 
struct line{
    double a, b, c;
}v[50005];
 
pi rotate(pi a, pi b, double q){
    int dx = a.second - b.second;
    int dy = b.first - a.first;
    double pyth = hypot(dx, dy);
    return pi(b.first + (dx / pyth) * q, b.second + (dy / pyth) * q);
}
 
pi cross(line p, line q){
    double base = p.a * q.b - p.b * q.a;
    if(fabs(base) < 1e-5) return pi(1e9, 1e9);
    return pi((p.b * q.c - q.b * p.c) / base, (p.c * q.a - q.c * p.a) / base);
}
 
bool ccw(pi a, pi b, pi c){
    double dx1 = b.first - a.first;
    double dy1 = b.second - a.second;
    double dx2 = c.first - a.first;
    double dy2 = c.second - a.second;
    return dx1 * dy2 > dy1 * dx2;
}
 
double func(line a, pi b){
    return a.a * b.first + a.b * b.second + a.c;
}

void half_plane_intersect(vector<pi> &ret){
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            pi crs = cross(v[i], v[j]);
            if(fabs(crs.first - 1e9) < 1e-4) continue;
            bool bad = 0;
            for(int k=0; k<n; k++){
                if(func(v[k], crs) < -1e-4){
                    bad = 1;
                    break;
                }
            }
            if(!bad) ret.push_back(crs);
        }
    }
 
}
 
bool trial(double d){
    for(int i=0; i<n; i++){
        int a = y[i] - y[i+1];
        int b = x[i+1] - x[i];
        pi loc = rotate(pi(x[i], y[i]), pi(x[i+1], y[i+1]), d);
        v[i] = {1.0 * a, 1.0 * b, - a * loc.first - b * loc.second}; // ax + by + c >= 0
    }
    vector<pi> p;
    half_plane_intersect(p);
    if(p.empty()) return 0;
    swap(p[0], *min_element(p.begin(), p.end()));
    sort(p.begin() + 1, p.end(), [&](const pi &a, const pi &b){
    	return ccw(p[0], a, b);
    });
    auto dist = [&](pi a, pi b){
    	return hypot(b.first - a.first, b.second - a.second);
    };
    int pt = 0;
    for(int i=0; i<p.size(); i++){
    	while(pt+1 < p.size() && dist(p[i], p[pt]) < dist(p[i], p[pt+1])){
    		pt++;
    	}
    	if(dist(p[i], p[pt]) >= 2 * d) return 1;
    }
    return 0;
}
 
int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d %d",&x[i],&y[i]);
    }
    x[n] = x[0], y[n] = y[0];
    double s = 0, e = 1e7;
    for(int i=0; i<50; i++){
        double m = (s+e)/2;
        if(trial(m)) s = m;
        else e = m;
    }
    printf("%.3f",s);
}

Compilation message (stderr)

2circles.cpp: In function 'bool trial(double)':
2circles.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<p.size(); i++){
                   ^
2circles.cpp:93:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while(pt+1 < p.size() && dist(p[i], p[pt]) < dist(p[i], p[pt+1])){
                 ^
2circles.cpp: In function 'int main()':
2circles.cpp:102:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
2circles.cpp:104:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x[i],&y[i]);
                                   ^

• Subtask 1: 40 / 100