#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<llf, llf> pi;
const llf eps = 1e-8;
int n;
int x[50005], y[50005];
struct line{
llf a, b, c;
}v[50005];
pi rotate(pi a, pi b, llf q){
int dx = a.second - b.second;
int dy = b.first - a.first;
llf pyth = hypot(dx, dy);
return pi(b.first + (dx / pyth) * q, b.second + (dy / pyth) * q);
}
pi cross(line p, line q){
auto func = [&](line a, pi b){
return a.a * b.first + a.b * b.second + a.c;
};
llf base = p.a * q.b - p.b * q.a;
if(fabs(base) < eps) return pi(1e9, 1e9);
pi ret = pi((p.b * q.c - q.b * p.c) / base, (p.c * q.a - q.c * p.a) / base);
return ret;
}
bool ccw(pi a, pi b, pi c){
llf dx1 = b.first - a.first;
llf dy1 = b.second - a.second;
llf dx2 = c.first - a.first;
llf dy2 = c.second - a.second;
return dx1 * dy2 > dy1 * dx2;
}
double tmp(pi a, pi b, pi c){
llf dx1 = b.first - a.first;
llf dy1 = b.second - a.second;
llf dx2 = c.first - a.first;
llf dy2 = c.second - a.second;
return dx1 * dy2 - dy1 * dx2;
}
int low(line a, line b, line c){
line l[3] = {a, b, c};
auto func = [&](line a, pi b){
return a.a * b.first + a.b * b.second + a.c;
};
int cnt = 0;
for(int i=0; i<3; i++){
for(int j=i+1; j<3; j++){
pi t = cross(l[i], l[j]);
if(fabs(t.first - 1e9) < eps) continue;
if(func(l[3-i-j], t) > 0){
cnt++;
}
}
}
if(cnt == 0) return -1;
if(cnt == 1) return 1;
return 0;
}
void get_points(vector<pi> &ret){
deque<line> dq;
for(int i=0; i<n; i++){
while(dq.size() >= 2){
int res = low(dq[dq.size()-2], dq.back(), v[i]);
if(res == -1) return;
if(res == 0) break;
dq.pop_back();
}
dq.push_back(v[i]);
}
while(dq.size() >= 3){
int res = low(dq[dq.size()-2], dq.back(), dq[0]);
if(res == -1) return;
if(res == 0) break;
dq.pop_back();
}
while(dq.size() >= 3){
int res = low(dq.back(), dq[0], dq[1]);
if(res == -1) return;
if(res == 0) break;
dq.pop_front();
}
if(dq.size() <= 2) return;
for(int i=0; i<dq.size()-1; i++){
ret.push_back(cross(dq[i], dq[i+1]));
}
ret.push_back(cross(dq.back(), dq.front()));
}
vector<pi> q;
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;
get_points(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);
});
q.clear();
for(auto &i : p){
while(q.size() >= 2 && !ccw(q[q.size()-2], q.back(), i)){
q.pop_back();
}
q.push_back(i);
}
p = q;
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
2circles.cpp: In function 'pi cross(line, line)':
2circles.cpp:40:7: warning: variable 'func' set but not used [-Wunused-but-set-variable]
auto func = [&](line a, pi b){
^
2circles.cpp: In function 'void get_points(std::vector<std::pair<long double, long double> >&)':
2circles.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<dq.size()-1; i++){
^
2circles.cpp: In function 'bool trial(double)':
2circles.cpp:142:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<p.size(); i++){
^
2circles.cpp:143:14: 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])) pt++;
^
2circles.cpp: In function 'int main()':
2circles.cpp:150:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
2circles.cpp:152:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x[i],&y[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4776 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4776 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4776 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4776 KB |
Output is correct |
| 5 |
Correct |
33 ms |
5036 KB |
Output is correct |
| 6 |
Correct |
216 ms |
6396 KB |
Output is correct |
| 7 |
Correct |
183 ms |
5628 KB |
Output is correct |
| 8 |
Correct |
203 ms |
5704 KB |
Output is correct |
| 9 |
Correct |
649 ms |
7040 KB |
Output is correct |
| 10 |
Incorrect |
886 ms |
9060 KB |
Output isn't correct |
