Submission #158863

#	Time	Username	Problem	Language	Result	Execution time	Memory
158863		georgerapeanu	2circles (balkan11_2circles)	C++11	10 / 100	66 ms	2436 KiB

twocircles

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int NMAX = 5e4;
int n;
pair<int,int> p[NMAX + 5];
pair<double,double> np[NMAX + 5];
pair<double,double> vec[NMAX + 5];
pair<double,double> gr;
pair<int,int> origin;

double sqr_dist(pair<double,double> p1,pair<double,double> p2){
    return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}

double det(pair<double,double> a,pair<double,double> b,pair<double,double> c){
    return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second);
}

void init(){
    for(int i = 1;i <= n;i++){
        vec[i].first = p[i % n + 1].first - p[i].first;
        vec[i].second = p[i % n + 1].second - p[i].second;
        swap(vec[i].first,vec[i].second);
        vec[i].first *= -1;
        double len = sqrt(vec[i].first * vec[i].first + vec[i].second * vec[i].second);
        vec[i].first = (vec[i].first / len);
        vec[i].second = (vec[i].second / len);
        if((gr.first - p[i].first) * vec[i].first + (gr.second - p[i].second) * vec[i].second < 0){
            vec[i].first *= -1;
            vec[i].second *= -1;
        }
    }
}

bool ok(double r){
    for(int i = 1;i <= n;i++){
        double a,b,c;
        double aa,bb,cc;

        pair<double,double> p1 = p[i == 1 ? n:i - 1];
        pair<double,double> p2 = p[i];
        
        p1.first += r * vec[i == 1 ? n:i - 1].first;
        p1.second += r * vec[i == 1 ? n:i - 1].second;
        
        p2.first += r * vec[i == 1 ? n:i - 1].first;
        p2.second += r * vec[i == 1 ? n:i - 1].second;

        a = (p2.second - p1.second);
        b = (-p2.first + p1.first);
        c = double(p2.first) * p1.second - double(p2.second) * p1.first;
        
        p1 = p[i];
        p2 = p[i % n + 1];
        
        p1.first += r * vec[i].first;
        p1.second += r * vec[i].second;
        
        p2.first += r * vec[i].first;
        p2.second += r * vec[i].second;
        
        aa = (p2.second - p1.second);
        bb = (-p2.first + p1.first);
        cc = double(p2.first) * p1.second - double(p2.second) * p1.first;

        np[i].second = (cc * a - c * aa) / (b * aa - bb * a);
        np[i].first = (cc * b - c * bb) / (a * bb - aa * b);
    }

    double area = 0;
    for(int i = 1;i <= n;i++){
        area += det(origin,np[i],np[i % n + 1]);
    }

    if(area < 0){
        return false;
    }

    int lst = 1;

    for(int i = 1;i <= n;i++){
        while(sqr_dist(np[i],np[lst]) < sqr_dist(np[i],np[lst % n + 1])){
            lst = lst % n + 1;
        }
        if(sqr_dist(np[i],np[lst]) >= 4 * r * r){
            return true;
        }
    }

    return false;
}

int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;i++){
        scanf("%d %d",&p[i].first,&p[i].second);
        origin.first = min(origin.first,p[i].first);
        origin.second = min(origin.second,p[i].second);
        gr.first += p[i].first;
        gr.second += p[i].second;
    }

    gr.first /= n;
    gr.second /= n;

    init();
    double st = 0,dr = 1e14;
    int lst = 1;

    for(int i = 1;i <= n;i++){
        dr = min(dr,sqr_dist(p[i],gr));
    }

    dr = sqrt(dr);

    while(dr - st > 1e-4){
        double mid = (st + dr) / 2;

        if(ok(mid)){
            st = mid;        
        }
        else{
            dr = mid;
        }
    }

    printf("%.4f\n",st);

    return 0;
}

Compilation message (stderr)

twocircles.cpp: In function 'int main()':
twocircles.cpp:114:9: warning: unused variable 'lst' [-Wunused-variable]
     int lst = 1;
         ^~~
twocircles.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
twocircles.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&p[i].first,&p[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 100