#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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
17 ms |
888 KB |
Output isn't correct |
| 7 |
Incorrect |
13 ms |
888 KB |
Output isn't correct |
| 8 |
Incorrect |
16 ms |
1016 KB |
Output isn't correct |
| 9 |
Incorrect |
50 ms |
1656 KB |
Output isn't correct |
| 10 |
Incorrect |
66 ms |
2436 KB |
Output isn't correct |
