Submission #101206

#	Time	Username	Problem	Language	Result	Execution time	Memory
101206		mraron	2circles (balkan11_2circles)	C++14	10 / 100	4099 ms	2056 KiB

twocircles

#include<bits/stdc++.h>
using namespace std;

#define xx first
#define yy second

const double PI=3.1415926535897932384626433832795;

typedef pair<double,double> pt;

int ccw(pt a, pt b, pt c) {
	b.xx-=a.xx;c.xx-=a.xx;
	b.yy-=a.yy;c.yy-=a.yy;
	
	if(b.yy*c.xx < c.yy*b.xx) {
		return -1;
	}else if(b.yy*c.xx == c.yy*b.xx) {
		return 0;
	}
	
	return 1;
}

double len(pt a) {
	return sqrt(a.xx*a.xx+a.yy*a.yy);
}

double dist(pt& a, pt& b) {
	return len({a.xx-b.xx, a.yy-b.yy});
}

pt egyseg(pt& a) {
	double l=len(a);
	return {a.xx/l, a.yy/l};
}

double angle(pt a, pt b, pt c) {
	a.xx-=b.xx;c.xx-=b.xx;
	a.yy-=b.yy;c.yy-=b.yy;
	return acos((a.xx*c.xx+a.yy*c.yy)/(len(a)*len(c)));
}

double diameter(vector<pt> &poly) {
	double ans=0.0;
	for(int i=0;i<(int)poly.size();++i) {
		for(int j=0;j<(int)poly.size();++j) {
			ans=max(ans, dist(poly[i], poly[j]));
		}
	}
	return ans;
}

bool intersect(pair<pt,pt> sz1, pair<pt,pt> sz2) {
	if(ccw(sz1.xx, sz1.yy, sz2.xx)==ccw(sz1.xx, sz1.yy, sz2.yy)) return false;
	if(ccw(sz2.xx, sz1.xx, sz1.yy)<0) swap(sz1.xx, sz1.yy);
	return ccw(sz2.xx, sz1.xx, sz2.yy)>=0 && ccw(sz2.xx, sz1.yy, sz2.yy)<=0; 
}

int main() {
	int n;
	cin>>n;
	
	vector<pt> t(n);
	for(int i=0;i<n;++i) cin>>t[i].xx>>t[i].yy;
	//cerr<<diameter(t)<<"\n";
	double L=0, R=diameter(t)/2;
	for(int it=0;it<=64;++it) {
		double mid=(L+R)/2;
		//cerr<<L<<" "<<R<<"\n";
		vector<pt> uj;
		for(int i=0;i<n;++i) {
			int a=(i-1+n)%n;
			int b=(i+1)%n;
			double alpha=angle(t[a], t[i], t[b]);
			double x=mid/cos(alpha-PI/2);
			pt v1={t[i].xx-t[a].xx, t[i].yy-t[a].yy};
			pt v2={t[i].xx-t[b].xx, t[i].yy-t[b].yy};
			v1=egyseg(v1);
			v2=egyseg(v2);
			uj.push_back({t[i].xx-x*(v1.xx+v2.xx), t[i].yy-x*(v1.yy+v2.yy)});
		}
		
		bool ok=true;
		for(int i=0;i<n;++i) {
			int a=(i+1)%n;
			ok&=!intersect({t[i], uj[i]}, {t[a], uj[a]});
		}
		
		if(diameter(uj)>=2*mid && ok) {
			L=mid;
		}else {
			R=mid;
		}
	}
	
	cout<<fixed<<setprecision(3)<<L<<"\n";
	
	
	return 0;
}

• Subtask 1: 10 / 100