Submission #650925

#	Time	Username	Problem	Language	Result	Execution time	Memory
650925		GusterGoose27	2circles (balkan11_2circles)	C++11	10 / 100	2646 ms	10408 KiB

twocircles

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

const int MAXN = 5e4;
const ld eps = 1e-8;
int n;

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

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

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

ld get_mag(pdd v) {
	return sqrt(v.first*v.first+v.second*v.second);
}

void normalize(pdd &v) {
	ld mag = get_mag(v);
	v = (1/mag)*v;
}

class Line {
public:
	pdd base;
	pdd vec;
	ld r_bound;
	Line() {}
	Line(pdd b, pdd v) {
		base = b;
		vec = v;
		normalize(vec);
	}
	Line shift(ld dist) { // shifting inwards, 90* from vec direction
		pdd start = base;
		return Line(base+dist*pdd(-vec.second, vec.first), vec);
	}
	ld dist_on_line(pdd p) {
		if (vec.first < eps) return (p.second-base.second)/vec.second;
		return (p.first-base.first)/vec.first;
	}
};

ld sin_diff(pdd a, pdd b) {
	return b.first*a.second-a.first*b.second;
}

pdd intersect(Line &a, Line &b) {
	pdd v3 = b.base-a.base;
	ld dist = get_mag(b.base-a.base);
	normalize(v3);
	dist *= sin_diff(b.vec, v3)/sin_diff(b.vec, a.vec);
	return a.base+dist*a.vec;
}

pdd points[MAXN];
pdd tempp[MAXN+5];
Line lines[MAXN];
Line templ[MAXN];
int botpos = -1;
int toppos = -1;

ld max_dist(int num) {
	int start = 0;
	ld best_mag = 0;
	for (int j; j < num; j++) {
		ld mag = get_mag(tempp[j]-tempp[0]);
		if (mag > best_mag) {
			start = j;
			best_mag = mag;
		}
	}
	int j = start;
	for (int i = 1; i < num; i++) {
		ld cur_dist = get_mag(tempp[j%num]-tempp[i]);
		ld nxt_dist = get_mag(tempp[(j+1)%num]-tempp[i]);
		while (nxt_dist > cur_dist) {
			j++;
			cur_dist = nxt_dist;
			nxt_dist = get_mag(tempp[(j+1)%num]-tempp[i]);
		}
		best_mag = max(best_mag, cur_dist);
	}
	return best_mag;
}

ld max_dist() {
	ld lbound = -1e9;
	ld rbound = 1e9;
	for (int i = 0; i < n; i++) {
		if (abs(templ[i].vec.first) < eps) {
			if (templ[i].vec.second > 0) rbound = templ[i].base.first;
			else lbound = templ[i].base.first;
		}
	}
	if (lbound > rbound) return 0;
	vector<int> bothull;
	vector<int> tophull;
	for (int j = botpos; j < botpos+n && templ[j%n].vec.first > eps; j++) {
		int i = j%n;
		if (bothull.empty()) {
			bothull.push_back(i);
			continue;
		}
		ld inter = intersect(templ[bothull.back()], templ[i]).first;
		while (bothull.size() > 1 && inter < templ[bothull[bothull.size()-2]].r_bound) {
			bothull.pop_back();
			inter = intersect(templ[bothull.back()], templ[i]).first;
		}
		templ[bothull.back()].r_bound = inter;
		bothull.push_back(i);
	}
	for (int j = toppos+n; j > toppos && templ[j%n].vec.first < -eps; j--) {
		int i = j%n;
		if (tophull.empty()) {
			tophull.push_back(i);
			continue;
		}
		ld inter = intersect(templ[tophull.back()], templ[i]).first;
		while (tophull.size() > 1 && inter < templ[tophull[tophull.size()-2]].r_bound) {
			tophull.pop_back();
			inter = intersect(templ[tophull.back()], templ[i]).first;
		}
		templ[tophull.back()].r_bound = inter;
		tophull.push_back(i);
	}
	int bstart = 0;
	int tstart = 0;
	int bend = bothull.size()-1;
	int tend = tophull.size()-1;
	while (bstart+1 < bothull.size() && templ[bothull[bstart]].r_bound < lbound) bstart++;
	while (tstart+1 < tophull.size() && templ[tophull[tstart]].r_bound < lbound) tstart++;
	while (bend > 0 && templ[bothull[bend-1]].r_bound > rbound) bend--;
	while (tend > 0 && templ[tophull[tend-1]].r_bound > rbound) tend--;
	if (abs(templ[tophull[tstart]].vec.second) > eps || abs(templ[bothull[bstart]].vec.second) > eps)
		lbound = max(lbound, intersect(templ[tophull[tstart]], templ[bothull[bstart]]).first);
	if (abs(templ[tophull[tend]].vec.second) > eps || abs(templ[bothull[bend]].vec.second) > eps)
		rbound = min(rbound, intersect(templ[tophull[tend]], templ[bothull[bend]]).first);
	if (lbound > rbound) return 0;
	int num = 0;
	Line lb(pdd(lbound, 0), pdd(0, -1));
	Line rb(pdd(rbound, 0), pdd(0, 1));
	for (int i = bstart; i < bend; i++) tempp[num++] = intersect(templ[bothull[i]], templ[bothull[i+1]]);
	tempp[num++] = intersect(templ[bothull[bend]], rb);
	tempp[num++] = intersect(templ[tophull[tend]], rb);
	for (int i = tend-1; i >= tstart; i--) tempp[num++] = intersect(templ[tophull[i]], templ[tophull[i+1]]);
	tempp[num++] = intersect(templ[tophull[tstart]], lb);
	tempp[num++] = intersect(templ[bothull[bstart]], lb);
	return max_dist(num);
}

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[i] = Line(points[i], points[(i+1)%n]-points[i]);
		if (lines[i].vec.first > eps && lines[(i+n-1)%n].vec.first < eps) botpos = i;
		if (lines[i].vec.first < -eps && lines[(i+1)%n].vec.first > -eps) toppos = i;
	}
	ld mn = 0;
	ld mx = 6e6;
	int iters = 500;
	for (int t = 0; t < iters; t++) {
		ld dist = (mn+mx)/2;
		for (int i = 0; i < n; i++) templ[i] = lines[i].shift(dist);
		if (max_dist() > 2*dist) mn = dist;
		else mx = dist;
	}
	cout << setprecision(20) << mn << "\n";
}

Compilation message (stderr)

twocircles.cpp: In member function 'Line Line::shift(ld)':
twocircles.cpp:46:7: warning: variable 'start' set but not used [-Wunused-but-set-variable]
   46 |   pdd start = base;
      |       ^~~~~
twocircles.cpp: In function 'ld max_dist()':
twocircles.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  while (bstart+1 < bothull.size() && templ[bothull[bstart]].r_bound < lbound) bstart++;
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~
twocircles.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  while (tstart+1 < tophull.size() && templ[tophull[tstart]].r_bound < lbound) tstart++;
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~
twocircles.cpp: In function 'ld max_dist(int)':
twocircles.cpp:77:11: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |  for (int j; j < num; j++) {
      |           ^
twocircles.cpp: In function 'int main()':
twocircles.cpp:34:7: warning: '<anonymous>.Line::r_bound' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 | class Line {
      |       ^~~~

• Subtask 1: 10 / 100