#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005;
const int offs = 1e9 + 100;
using pi = pair<int, int>;
const double eps = 1e-8;
typedef pair<long double, long double> pi;
namespace hpi{
bool z(long double x){ return fabs(x) < eps; }
struct line{
long double a, b, c;
bool operator<(const line &l)const{
bool flag1 = pi(a, b) > pi(0, 0);
bool flag2 = pi(l.a, l.b) > pi(0, 0);
if(flag1 != flag2) return flag1 > flag2;
long double t = ccw(pi(0, 0), pi(a, b), pi(l.a, l.b));
return z(t) ? c * hypot(l.a, l.b) < l.c * hypot(a, b) : t > 0;
}
pi slope(){ return pi(a, b);}
};
pi cross(line a, line b){
long double det = a.a * b.b - b.a * a.b;
return pi((a.c * b.b - a.b * b.c) / det, (a.a * b.c - a.c * b.a) / det);
}
bool bad(line a, line b, line c){
if(ccw(pi(0, 0), a.slope(), b.slope()) <= 0) return false;
pi crs = cross(a, b);
return crs.first * c.a + crs.second * c.b >= c.c;
}
bool solve(vector<line> v, vector<pi> &solution){ // ax + by <= c;
sort(v.begin(), v.end());
deque<line> dq;
for(auto &i : v){
if(!dq.empty() && z(ccw(pi(0, 0), dq.back().slope(), i.slope()))) continue;
while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), i)) dq.pop_back();
while(dq.size() >= 2 && bad(i, dq[0], dq[1])) dq.pop_front();
dq.push_back(i);
}
while(dq.size() > 2 && bad(dq[dq.size()-2], dq.back(), dq[0])) dq.pop_back();
while(dq.size() > 2 && bad(dq.back(), dq[0], dq[1])) dq.pop_front();
vector<pi> tmp;
for(int i=0; i<dq.size(); i++){
line cur = dq[i], nxt = dq[(i+1)%dq.size()];
if(ccw(pi(0, 0), cur.slope(), nxt.slope()) <= eps) return false;
tmp.push_back(cross(cur, nxt));
}
solution = tmp;
return true;
}
};
int x[MAXN], y[MAXN], n;
pi sub(vector<pi> &v, int x, int y){
x %= v.size(), y %= v.size();
return pi(v[y].first - v[x].first, v[y].second - v[x].second);
}
double dist(pi a, pi b){
return hypot(b.second - a.second, b.first - a.first);
}
bool trial(double t){
vector<hpi::line> v;
for(int i=0; i<n; i++){
double a = y[i+1] - y[i];
double b = x[i] - x[i+1];
double c = a * x[i] + b * y[i] - hypot(a, b) * t;
v.push_back({a, b, c});
}
vector<pi> w;
if(!hpi::solve(v, w)){
return false;
}
int p = 0;
double ret = 0;
for(int i=0; i<w.size(); i++){
while(ccw(pi(0, 0), sub(w, p+1, p), sub(w, i, i+1)) > -eps){
ret = max(ret, dist(w[i], w[p]));
p = (p+1)%w.size();
ret = max(ret, dist(w[i], w[p]));
}
ret = max(ret, dist(w[i], w[p]));
}
return ret >= 2 * t;
}
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
twocircles.cpp:8:40: error: conflicting declaration 'typedef struct std::pair<long double, long double> pi'
typedef pair<long double, long double> pi;
^~
twocircles.cpp:5:26: note: previous declaration as 'using pi = struct std::pair<int, int>'
using pi = pair<int, int>;
^
twocircles.cpp: In member function 'bool hpi::line::operator<(const hpi::line&) const':
twocircles.cpp:17:20: error: 'ccw' was not declared in this scope
long double t = ccw(pi(0, 0), pi(a, b), pi(l.a, l.b));
^~~
twocircles.cpp: In function 'bool hpi::bad(hpi::line, hpi::line, hpi::line)':
twocircles.cpp:27:6: error: 'ccw' was not declared in this scope
if(ccw(pi(0, 0), a.slope(), b.slope()) <= 0) return false;
^~~
twocircles.cpp: In function 'bool hpi::solve(std::vector<hpi::line>, std::vector<std::pair<int, int> >&)':
twocircles.cpp:35:24: error: 'ccw' was not declared in this scope
if(!dq.empty() && z(ccw(pi(0, 0), dq.back().slope(), i.slope()))) continue;
^~~
twocircles.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<dq.size(); i++){
~^~~~~~~~~~
twocircles.cpp:45:7: error: 'ccw' was not declared in this scope
if(ccw(pi(0, 0), cur.slope(), nxt.slope()) <= eps) return false;
^~~
twocircles.cpp: In function 'bool trial(double)':
twocircles.cpp:80:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<w.size(); i++){
~^~~~~~~~~
twocircles.cpp:81:9: error: 'ccw' was not declared in this scope
while(ccw(pi(0, 0), sub(w, p+1, p), sub(w, i, i+1)) > -eps){
^~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
twocircles.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x[i],&y[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~
