답안 #123486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123486 2019-07-01T13:56:26 Z tmwilliamlin168 두 개의 원 (balkan11_2circles) C++14
90 / 100
1031 ms 15316 KB
#include <bits/stdc++.h>
using namespace std;

#define ld long double

const int mxN=5e4;
int n, x[mxN], y[mxN];

vector<array<ld, 2>> convexHull(vector<array<ld, 2>> l, ld xl, ld xr) {
	sort(l.begin(), l.end(), greater<array<ld, 2>>());
	vector<array<ld, 2>> v, p;
	for(array<ld, 2> li : l) {
		while(v.size()>1&&(v.back()[1]-v[v.size()-2][1])/(v[v.size()-2][0]-v.back()[0])>(li[1]-v.back()[1])/(v.back()[0]-li[0]))
			v.pop_back();
		v.push_back(li);
	}
	int jl=0;
	while(jl+1<v.size()&&v[jl+1][0]*xl+v[jl+1][1]<v[jl][0]*xl+v[jl][1])
		++jl;
	p.push_back({xl, v[jl][0]*xl+v[jl][1]});
	int jr=jl;
	while(jr+1<v.size()&&v[jr+1][0]*xr+v[jr+1][1]<v[jr][0]*xr+v[jr][1])
		++jr;
	for(int i=jl; i+1<=jr; ++i) {
		ld x=(v[i+1][1]-v[i][1])/(v[i][0]-v[i+1][0]), y=v[i][0]*x+v[i][1];
		p.push_back({x, y});
	}
	p.push_back({xr, v[jr][0]*xr+v[jr][1]});
	return p;
}

ld gy(array<ld, 2> p1, array<ld, 2> p2, ld x) {
	return p1[1]+(p2[1]-p1[1])/(p2[0]-p1[0])*(x-p1[0]);
}

array<ld, 2> segmentIntersection(array<ld, 2> a, array<ld, 2> b, array<ld, 2> c, array<ld, 2> d) {
	ld x=(gy(c, d, 0)-gy(a, b, 0))/((a[1]-b[1])/(a[0]-b[0])-(c[1]-d[1])/(c[0]-d[0]));
	return {x, gy(a, b, x)};
}

vector<array<ld, 2>> halfplaneIntersection(vector<array<array<ld, 2>, 2>> a, ld xl, ld xr) {
	if(xl>xr)
		return vector<array<ld, 2>>();
	vector<array<ld, 2>> tl, bl;
	for(array<array<ld, 2>, 2> ai : a) {
		if(ai[0][0]>ai[1][0]) {
			tl.push_back({(ai[1][1]-ai[0][1])/(ai[1][0]-ai[0][0])});
			tl.back()[1]=gy(ai[0], ai[1], 0);
		} else {
			ai[0][1]=-ai[0][1];
			ai[1][1]=-ai[1][1];
			bl.push_back({(ai[1][1]-ai[0][1])/(ai[1][0]-ai[0][0])});
			bl.back()[1]=gy(ai[0], ai[1], 0);
		}
	}
	/*
	cout << "top lines" << endl;
	for(array<ld, 2> ai : tl)
		cout << ai[0] << " " << ai[1] << endl;
	cout << "bottom lines" << endl;
	for(array<ld, 2> ai : bl)
		cout << ai[0] << " " << ai[1] << endl;
	//*/
	vector<array<ld, 2>> tp=convexHull(tl, xl, xr), bp=convexHull(bl, xl, xr);
	for(array<ld, 2> &p : bp)
		p[1]=-p[1];
	/*
	cout << "top points" << endl;
	for(array<ld, 2> pi : tp)
		cout << pi[0] << " " << pi[1] << endl;
	cout << "bottom points" << endl;
	for(array<ld, 2> pi : bp)
		cout << pi[0] << " " << pi[1] << endl;
	//*/
	vector<array<ld, 2>> tp2, bp2;
	int i1=0, i2=0;
	if(tp[0][1]<bp[0][1]) {
		i1=i2=1;
		while(i1<tp.size()&&i2<bp.size()) {
			if(tp[i1][0]<bp[i2][0]) {
				if(tp[i1][1]>gy(bp[i2-1], bp[i2], tp[i1][0])) {
					tp2.push_back(segmentIntersection(tp[i1-1], tp[i1], bp[i2-1], bp[i2]));
					break;
				}
				++i1;
			} else {
				if(bp[i2][1]<gy(tp[i1-1], tp[i1], bp[i2][0])) {
					tp2.push_back(segmentIntersection(tp[i1-1], tp[i1], bp[i2-1], bp[i2]));
					//cout << "fi" << endl;
					//cout << tp2.back()[0] << " " << tp2.back()[1] << endl;
					break;
				}
				++i2;
			}
		}
	}
	if(i1>=tp.size()||i2>=bp.size())
		return vector<array<ld, 2>>();
	if(tp.back()[1]<bp.back()[1]) {
		while(1) {
			if(tp[i1][0]<bp[i2][0]) {
				if(tp[i1][1]<gy(bp[i2-1], bp[i2], tp[i1][0])) {
					tp2.push_back(segmentIntersection(tp[i1-1], tp[i1], bp[i2-1], bp[i2]));
					break;
				}
				tp2.push_back(tp[i1++]);
			} else {
				if(bp[i2][1]>gy(tp[i1-1], tp[i1], bp[i2][0])) {
					tp2.push_back(segmentIntersection(tp[i1-1], tp[i1], bp[i2-1], bp[i2]));
					break;
				}
				bp2.push_back(bp[i2++]);
			}
		}
	} else {
		while(i1<tp.size())
			tp2.push_back(tp[i1++]);
		while(i2<bp.size())
			bp2.push_back(bp[i2++]);
	}
	reverse(tp2.begin(), tp2.end());
	tp2.insert(tp2.end(), bp2.begin(), bp2.end());
	return tp2;
}

pair<ld, int> findOpt(vector<array<ld, 2>> &p, int m1, int l2, int r2) {
	pair<ld, int> q{0, l2};
	for(int i=l2; i<=r2; ++i)
		q=max(make_pair(hypot(p[i][0]-p[m1][0], p[i][1]-p[m1][1]), i), q);
	return q;
}

ld dc(vector<array<ld, 2>> &p, int l1, int r1, int l2, int r2) {
	if(l1>r1)
		return 0;
	int m1=(l1+r1)/2;
	pair<ld, int> q=findOpt(p, m1, l2, r2);
	return max({q.first, dc(p, l1, m1-1, l2, q.second), dc(p, m1+1, r1, q.second, r2)});
}

bool chk(ld r) {
	vector<array<array<ld, 2>, 2>> a;
	ld xl=-1e8, xr=1e8;
	for(int i=0; i<n; ++i) {
		int j=(i+1)%n;
		if(x[i]==x[j]) {
			if(y[i]>y[j])
				xl=max(x[i]+r, xl);
			else
				xr=min(x[i]-r, xr);
		} else {
			ld sm=hypot(x[j]-x[i], y[j]-y[i]), tx=-(y[j]-y[i])*r/sm, ty=(x[j]-x[i])*r/sm;
			a.push_back({{{x[i]+tx, y[i]+ty}, {x[j]+tx, y[j]+ty}}});
		}
	}
	vector<array<ld, 2>> p=halfplaneIntersection(a, xl, xr);
	/*
	cout << "new poly" << endl;
	for(array<ld, 2> a : p)
		cout << a[0] << " " << a[1] << endl;
	//*/
	if(!p.size())
		return 0;
	pair<ld, int> q=findOpt(p, 0, 0, p.size()-1);
	return dc(p, 0, q.second-1, q.second, p.size()-1)>2*r;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> x[i] >> y[i];
	//cout << chk(0.5);
	//return 0;
	ld lb=0, rb=3e7;
	while(rb-lb>1e-4) {
		ld mb=(lb+rb)/2;
		//cout << "chk " << mb << endl;
		if(chk(mb))
			lb=mb;
		else
			rb=mb;
	}
	cout << fixed << setprecision(3) << lb;
}

Compilation message

twocircles.cpp: In function 'std::vector<std::array<long double, 2> > convexHull(std::vector<std::array<long double, 2> >, long double, long double)':
twocircles.cpp:18:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(jl+1<v.size()&&v[jl+1][0]*xl+v[jl+1][1]<v[jl][0]*xl+v[jl][1])
        ~~~~^~~~~~~~~
twocircles.cpp:22:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(jr+1<v.size()&&v[jr+1][0]*xr+v[jr+1][1]<v[jr][0]*xr+v[jr][1])
        ~~~~^~~~~~~~~
twocircles.cpp: In function 'std::vector<std::array<long double, 2> > halfplaneIntersection(std::vector<std::array<std::array<long double, 2>, 2> >, long double, long double)':
twocircles.cpp:79:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i1<tp.size()&&i2<bp.size()) {
         ~~^~~~~~~~~~
twocircles.cpp:79:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i1<tp.size()&&i2<bp.size()) {
                       ~~^~~~~~~~~~
twocircles.cpp:97:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(i1>=tp.size()||i2>=bp.size())
     ~~^~~~~~~~~~~
twocircles.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(i1>=tp.size()||i2>=bp.size())
                    ~~^~~~~~~~~~~
twocircles.cpp:116:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i1<tp.size())
         ~~^~~~~~~~~~
twocircles.cpp:118:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i2<bp.size())
         ~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 40 ms 1232 KB Output is correct
6 Correct 275 ms 3504 KB Output is correct
7 Correct 156 ms 4124 KB Output is correct
8 Correct 212 ms 5036 KB Output is correct
9 Correct 606 ms 8840 KB Output is correct
10 Correct 1031 ms 15316 KB Output is correct