Submission #31960

#	Time	Username	Problem	Language	Result	Execution time	Memory
31960		gs14004	2circles (balkan11_2circles)	C++14	70 / 100	4000 ms	6912 KiB

twocircles

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
const int MAXN = 50005;

typedef pair<double, double> pi;
namespace hpi{
	const double eps = 1e-6;
	double 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;
	}
	bool z(double x){ return fabs(x) < eps; }
	struct line{
		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;
			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){
		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){
		pi crs = cross(a, b);
		return crs.first * c.a + crs.second * c.b >= c.c - eps;
	}
	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() && ccw(pi(0, 0), dq.back().slope(), i.slope()) <= eps) return false;
			while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), i)) dq.pop_back();
			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;

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;
	}
	double mx = 0;
	for(auto &i : w){
		for(auto &j : w){
			mx = max(mx, hypot(i.first - j.first, i.second - j.second));
		}
	}
	return mx >= 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 (stderr)

2circles.cpp: In function 'bool hpi::solve(std::vector<hpi::line>, std::vector<std::pair<double, double> >&)':
2circles.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<dq.size(); i++){
                 ^
2circles.cpp: In function 'int main()':
2circles.cpp:81:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
2circles.cpp:83: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]);
                             ^

• Subtask 1: 70 / 100