Submission #153698

#	Time	Username	Problem	Language	Result	Execution time	Memory
153698		junodeveloper	2circles (balkan11_2circles)	C++14	100 / 100	761 ms	5732 KiB

twocircles

#include "bits/stdc++.h"
#define SZ(x) ((int)x.size())
using namespace std;
struct point {
	double x, y;
	point() {}
	point(double x, double y) : x(x), y(y) {}
	bool operator<(const point& b) const {
		return x == b.x ? y < b.y : x < b.x;
	}
};
struct Line {
	point s, t;
	Line() {}
	Line(point s, point t) : s(s), t(t) {}
};
double cross(point& a, point& b, point& c) {
	return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
}
double dirCross(Line& a, Line& b) {
	return (a.t.y - a.s.y) * (b.t.x - b.s.x) - (b.t.y - b.s.y) * (a.t.x - a.s.x);
}
point getIntersect(Line& a, Line& b) {
	double det = dirCross(a, b);
	double dx = b.s.x - a.s.x;
	double dy = b.s.y - a.s.y;
	double v = (-(b.t.y - b.s.y) * dx + (b.t.x - b.s.x) * dy) / det;
	return point(a.s.x + v * (a.t.x - a.s.x), a.s.y + v * (a.t.y - a.s.y));
}
bool isIncluded(Line& ln, point p) {
	return cross(ln.s, ln.t, p) >= 0;
}

vector<point> HPI(vector<Line>& ln) {
	deque<Line> dq;
	for(int i=0; i<SZ(ln); i++) {
		while(dq.size() >= 2 && !isIncluded(ln[i], getIntersect(dq[dq.size()-2], dq.back())))
			dq.pop_back();
		while(dq.size() >= 2 && !isIncluded(ln[i], getIntersect(dq[0], dq[1])))
			dq.pop_front();
		if(dq.size() < 2 || isIncluded(dq[0], getIntersect(dq.back(), ln[i])))
        	dq.push_back(ln[i]);
	}
	vector<point> res;
	if(dq.size() >= 3) for(int i=0; i<dq.size(); i++)
		res.push_back(getIntersect(dq[i], dq[(i+1)%dq.size()]));
	return res;
}
double calipers(vector<point>& ch) {
	double mn = 9e18, mx = -9e18, res = 0;
	int lm, rm;
	for(int i=0; i<SZ(ch); i++) {
		if(mn > ch[i].x) mn = ch[i].x, lm = i;
		if(mx < ch[i].x) mx = ch[i].x, rm = i;
	}
	int i1 = lm, i2 = rm;
	while(i1 != rm || i2 != lm) {
		res = max(res, hypot(ch[i1].x - ch[i2].x, ch[i1].y - ch[i2].y));
		if(i1 == rm) i2 = (i2 + 1) % SZ(ch);
		else if(i2 == lm) i1 = (i1 + 1) % SZ(ch);
		else {
			int ni1 = (i1 + 1) % SZ(ch);
			int ni2 = (i2 + 1) % SZ(ch);
			if((ch[ni1].y - ch[i1].y) * (ch[ni2].x - ch[i2].x) >
				(ch[ni2].y - ch[i2].y) * (ch[ni1].x - ch[i1].x))
				i1 = ni1;
			else i2 = ni2;
		}
	}
	return res;
}

int main() {
	int n;
	vector<point> p;
	scanf("%d", &n);
	for(int i=0,x,y; i<n; i++) {
		scanf("%d%d", &x, &y);
		p.push_back(point(x, y));
	}
	double lo = 0, hi = 1e9;
	for(int tt=0; tt<100; tt++) {
		double mid = (lo + hi) / 2;
		vector<Line> ln;
		for(int i=0; i<n; i++) {
			double dx = -(p[(i+1)%n].y - p[i].y);
			double dy = p[(i+1)%n].x - p[i].x;
			double sz = hypot(dx, dy);
			dx = dx / sz * mid, dy = dy / sz * mid;
			ln.push_back(Line(point(p[i].x + dx, p[i].y + dy), 
				point(p[(i+1)%n].x + dx, p[(i+1)%n].y + dy)));
		}
		vector<point> ch = HPI(ln);
		if(ch.size() >= 3) {
			double d = calipers(ch);
			if(d >= mid * 2) lo = mid;
			else hi = mid;
		} else hi = mid;
	}
	printf("%.3f", lo);
	return 0;
}

Compilation message (stderr)

twocircles.cpp: In function 'std::vector<point> HPI(std::vector<Line>&)':
twocircles.cpp:45:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(dq.size() >= 3) for(int i=0; i<dq.size(); i++)
                                  ~^~~~~~~~~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
twocircles.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
twocircles.cpp: In function 'double calipers(std::vector<point>&)':
twocircles.cpp:59:3: warning: 'rm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(i1 == rm) i2 = (i2 + 1) % SZ(ch);
   ^~
twocircles.cpp:60:8: warning: 'lm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   else if(i2 == lm) i1 = (i1 + 1) % SZ(ch);
        ^~

• Subtask 1: 100 / 100