답안 #667820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667820 2022-12-02T06:02:33 Z GusterGoose27 두 개의 원 (balkan11_2circles) C++11
100 / 100
412 ms 12112 KB
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef pair<ld, ld> pii;
ld inf = 1e9;
ld eps = 1e-8;

const int MAXN = 5e4;

pii operator+(pii a, pii b) {
	return pii(a.first+b.first, a.second+b.second);
}

ld cross(pii a, pii b) {
	return a.first*b.second-a.second*b.first;
}

ld dot(pii a, pii b) {
	return a.first*b.first+a.second*b.second;
}

pii operator-(pii a, pii b) {
	return pii(a.first-b.first, a.second-b.second);
}

pii operator*(pii a, ld b) {
	return pii(a.first*b, a.second*b);
}

pii operator/(pii a, ld b) {
	return a*(1/b);
}

pii operator*(ld b, pii a) {
	return a*b;
}

pii operator-(pii a) {
	return (-1)*a;
}

ld mag(pii a) {
	return sqrt(dot(a, a));
}

class Line {
public:
	pii start;
	pii vec;
	// ld rbound = inf;
	ld lbound = -inf;
	Line() {}
	Line(pii a, pii b) {
		start = a;
		vec = (b-a)/mag(b-a);
	}
	Line(Line other, ld x) {
		vec = other.vec;
		start = other.start+x*pii(-vec.second, vec.first);
	}
	pii get_point() {
		// assert(rbound < inf-eps);
		return start+vec*lbound;
	}
};

ld cross(Line a, Line b) {
	return cross(a.vec, b.vec);
}

pii points[MAXN];
Line lines[MAXN];
Line lines_orig[MAXN];
pii points_temp[MAXN];
int n;

ld mx_dist(int f, int t) {
	int s = f;
	ld best = 0;
	for (int i = f; i < t; i++) {
		while (s < t-1 && mag(points_temp[i]-points_temp[s]) < mag(points_temp[i]-points_temp[s+1])) s++;
		best = max(best, mag(points_temp[i]-points_temp[s]));
	}
	return best;
}

ld inter(Line a, Line b) { // distance in direction of vec from start of a
	return cross(b.start-a.start, b.vec)/cross(a.vec, b.vec);
}

bool possible(ld cur) {
	vector<int> hull;
	hull.push_back(0);
	for (int i = 1; i < n; i++) {
		if (cross(lines[hull.back()], lines[i]) < eps) return 0;
		while (hull.size() > 1 && cross(lines[i].vec, lines[hull.back()].get_point()-lines[i].start) < eps) {
			hull.pop_back();
			if (cross(lines[hull.back()], lines[i]) < eps) return 0;
		}
		lines[i].lbound = inter(lines[i], lines[hull.back()]);
		hull.push_back(i);
	} // now check collisions between front & back
	int s = 0;
	bool b1 = cross(lines[hull[s]].vec, lines[hull.back()].get_point()-lines[hull[s]].start) < eps;
	bool b2 = cross(lines[hull.back()].vec, lines[hull[s+1]].get_point()-lines[hull.back()].start) < eps;
	while (hull.size() > 3 && (b1 || b2)) {
		if (b1) {
			hull.pop_back();
		}
		if (b2) {
			s++;
		}
		b1 = cross(lines[hull[s]].vec, lines[hull.back()].get_point()-lines[hull[s]].start) < eps;
		b2 = cross(lines[hull.back()].vec, lines[hull[s+1]].get_point()-lines[hull.back()].start) < eps;
	}
	lines[hull[s]].lbound = inter(lines[hull[s]], lines[hull.back()]);
	for (int i = s; i < hull.size(); i++) points_temp[i] = lines[hull[i]].get_point();
	return (mx_dist(s, hull.size()) > 2*cur);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> points[i].first >> points[i].second;
	for (int i = 0; i < n; i++) {
		lines_orig[i] = Line(points[i], points[(i+1)%n]);
	}
	ld mn = 0;
	ld mx = 6e6;
	for (int i = 0; i < 100; i++) {
		ld cur = (mn+mx)/2;
		for (int i = 0; i < n; i++) lines[i] = Line(lines_orig[i], cur);
		if (possible(cur)) mn = cur;
		else mx = cur;
	}
	cout << fixed << setprecision(3) << mn << "\n";
}

Compilation message

twocircles.cpp: In function 'bool possible(ld)':
twocircles.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for (int i = s; i < hull.size(); i++) points_temp[i] = lines[hull[i]].get_point();
      |                  ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8164 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 7 ms 8172 KB Output is correct
4 Correct 7 ms 8148 KB Output is correct
5 Correct 28 ms 8232 KB Output is correct
6 Correct 92 ms 8940 KB Output is correct
7 Correct 98 ms 8876 KB Output is correct
8 Correct 141 ms 9032 KB Output is correct
9 Correct 252 ms 10648 KB Output is correct
10 Correct 412 ms 12112 KB Output is correct