Submission #146047

#	Time	Username	Problem	Language	Result	Execution time	Memory
146047		TadijaSebez	2circles (balkan11_2circles)	C++11	10 / 100	4027 ms	1596 KiB

twocircles

#include <bits/stdc++.h>
using namespace std;
#define ldb double
#define mp make_pair
#define pb push_back
const ldb PI=acos(-1);
const ldb eps=1e-8;
struct pt{ ldb x,y;pt(){}pt(ldb a, ldb b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
pt operator + (pt a, pt b){ return pt(a.x+b.x,a.y+b.y);}
pt operator * (pt a, ldb b){ return pt(a.x*b,a.y*b);}
pt operator / (pt a, ldb b){ return pt(a.x/b,a.y/b);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
ldb cross(pt a, pt b){ return a.x*b.y-a.y*b.x;}
ldb dot(pt a, pt b){ return a.x*b.x+a.y*b.y;}
ldb sq(pt a){ return dot(a,a);}
ldb abs(pt a){ return sqrt(sq(a));}
ldb dist(pt a, pt b){ return abs(a-b);}
vector<pt> ConvexHull(vector<pt> a)
{
	sort(a.begin(),a.end());
	bool ok=1;
	for(int i=2;i<a.size();i++) if(cross(a[i+2]-a[i],a[i+1]-a[i])!=0) ok=0;
	if(ok) return {a.front(),a.back()};
	vector<pt> h;int sz=0;
	for(int t=0;t<2;t++)
	{
		int p=sz+1;
		for(int i=0;i<a.size();i++)
		{
			while(sz>p && cross(a[i]-h[sz-2],h[sz-1]-h[sz-2])>=0) h.pop_back(),sz--;
			h.pb(a[i]);sz++;
		}
		h.pop_back();sz--;
		reverse(a.begin(),a.end());
	}
	return h;
}
ldb Diameter(vector<pt> a)
{
	int n=a.size();
	auto nxt=[&](int x){ return x==n-1?0:x+1;};
	auto pre=[&](int x){ return x==0?n-1:x-1;};
	ldb ans=0;
	for(int i=0,ptr=0;i<n;i++)
	{
		while(dist(a[i],a[ptr])<dist(a[i],a[nxt(ptr)])) ptr=nxt(ptr);
		while(dist(a[i],a[ptr])<dist(a[i],a[pre(ptr)])) ptr=pre(ptr);
		ans=max(ans,dist(a[i],a[ptr]));
	}
	return ans;
}
pair<bool,pt> Get(pt A, pt B, pt C, ldb r)
{
	ldb side=min(dist(A,B),dist(C,B));
    A=A-B;A=A/abs(A);
    C=C-B;C=C/abs(C);
    pt D=A+C;D=D/abs(D);
    //printf("A(%f %f) B(%f %f) C(%f %f) D(%f %f)\n",A.x,A.y,B.x,B.y,C.x,C.y,D.x,D.y);
    ldb sin_ang=abs(cross(A,D))/abs(A)/abs(D);
    ldb cos_ang=dot(A,D)/abs(A)/abs(D);
    ldb len=r/sin_ang;
    D=D*len;
    bool ok=1;
    if(r*cos_ang>side) ok=0;
    //printf("A(%f %f) B(%f %f) C(%f %f) D(%f %f)\n",A.x,A.y,B.x,B.y,C.x,C.y,D.x,D.y);
    return {ok,D+B};
}
vector<pt> a;
ldb dist(pt P, pt a, pt b)
{
	pt v=a-b;
	ldb c=cross(v,a);
	if(dot(v,a)>dot(v,b)) swap(a,b);
	if(dot(v,a)<=dot(v,P) && dot(v,P)<=dot(v,b)) return abs((cross(v,P)-c)/abs(v));
	return min(dist(P,a),dist(P,b));
}
bool Check(pt P, ldb r)
{
	for(int i=1;i<a.size();i++) if(dist(P,a[i-1],a[i])+eps<r) return 0;
	if(dist(P,a[0],a.back())+eps<r) return 0;
	return 1;
}
bool Check(ldb r)
{
	int n=a.size();
	auto nxt=[&](int x){ return x==n-1?0:x+1;};
	auto pre=[&](int x){ return x==0?n-1:x-1;};
	vector<pt> O;
	for(int i=0;i<n;i++)
	{
		auto P=Get(a[pre(i)],a[i],a[nxt(i)],r);
		if(P.first && Check(P.second,r)) O.pb(P.second);
	}
	if(O.size()<2) return 0;
	//printf("R: %.3f\n",r);
	//for(int i=0;i<n;i++) printf("(%.3f %.3f) ",O[i].x,O[i].y);
	//printf("\n");
	O=ConvexHull(O);
	//printf("Hull:\n");
	//for(int i=0;i<n;i++) printf("(%.3f %.3f) ",O[i].x,O[i].y);
	//printf("Diam: %.3f\n",Diameter(O));
	return Diameter(O)>=2*r;
}
int main()
{
	int n,x,y;
	scanf("%i",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i",&x,&y);
		a.pb(pt(x,y));
	}
	ldb top=2e7,bot=0,mid;
	while(top-bot>0.001)
	{
		mid=(top+bot)/2;
		if(Check(mid)) bot=mid;
		else top=mid;
	}
	printf("%.3f\n",(top+bot)/2);
	return 0;
}

Compilation message (stderr)

twocircles.cpp: In function 'std::vector<pt> ConvexHull(std::vector<pt>)':
twocircles.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=2;i<a.size();i++) if(cross(a[i+2]-a[i],a[i+1]-a[i])!=0) ok=0;
              ~^~~~~~~~~
twocircles.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<a.size();i++)
               ~^~~~~~~~~
twocircles.cpp: In function 'bool Check(pt, double)':
twocircles.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<a.size();i++) if(dist(P,a[i-1],a[i])+eps<r) return 0;
              ~^~~~~~~~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
twocircles.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 100