Submission #17561

#	Time	Username	Problem	Language	Result	Execution time	Memory
17561		gs14004	2circles (balkan11_2circles)	C++14	90 / 100	3219 ms	8948 KiB

twocircles

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<llf, llf> pi;
const llf eps = 1e-8;
 
int n;
int x[50005], y[50005];
 
struct line{
	llf a, b, c;
}v[50005];

bool colinear(line p, line q){
	llf base = p.a * q.b - p.b * q.a;
	return base >= -eps && base <= eps;
}

pi cross(line p, line q, double d){
	llf base = p.a * q.b - p.b * q.a;
	p.c -= d * hypot(p.a, p.b);
	q.c -= d * hypot(q.a, q.b);
	pi ret = pi((p.b * q.c - q.b * p.c) / base, (p.c * q.a - q.c * p.a) / base);
	return ret;
}
 
bool ccw(pi a, pi b, pi c){
	llf dx1 = b.first - a.first;
	llf dy1 = b.second - a.second;
	llf dx2 = c.first - a.first;
	llf dy2 = c.second - a.second;
	return dx1 * dy2 > dy1 * dx2;
}

int low(line a, line b, line c, llf d){
	line l[3] = {a, b, c};
	auto func = [&](line a, pi b){
		return (a.a * b.first + a.b * b.second + a.c) / hypot(a.a, a.b);
	};
	int cnt = 0;
	for(int i=0; i<3; i++){
		for(int j=i+1; j<3; j++){
			if(colinear(l[i], l[j])) continue;
			if(func(l[3-i-j], cross(l[i], l[j], d)) > d){
				cnt++;
			}
		}
	}
	if(cnt == 0) return -1;
	if(cnt == 1) return 1;
	return 0;
}
 
void get_points(vector<pi> &ret, double d){
	deque<line> dq;
	for(int i=0; i<n; i++){
		while(dq.size() >= 2){
			int res = low(dq[dq.size()-2], dq.back(), v[i], d);
			if(res == -1) return;
			if(res == 0) break;
			dq.pop_back();
		}
		dq.push_back(v[i]);
	}
	while(dq.size() >= 3){
		int res = low(dq[dq.size()-2], dq.back(), dq[0], d);
		if(res == -1) return;
		if(res == 0) break;
		dq.pop_back();
	}
	while(dq.size() >= 3){
		int res = low(dq.back(), dq[0], dq[1], d);
		if(res == -1) return;
		if(res == 0) break;
		dq.pop_front();
	}
	if(dq.size() <= 2) return;
	for(int i=0; i<dq.size()-1; i++){
		ret.push_back(cross(dq[i], dq[i+1], d));
	}
	ret.push_back(cross(dq.back(), dq.front(), d));
}

void calibrate_precision(vector<pi> &p){
	vector<pi> q;
	swap(p[0], *min_element(p.begin(), p.end()));
	sort(p.begin() + 1, p.end(), [&](const pi &a, const pi &b){
		return ccw(p[0], a, b);
	});
	for(auto &i : p){
		while(q.size() >= 2 && !ccw(q[q.size()-2], q.back(), i)){
			q.pop_back();
		}
		q.push_back(i);
	}
	p = q;
} // fuck you.

bool trial(double d){
	vector<pi> p;
	get_points(p, d);
	if(p.empty()) return 0;
	calibrate_precision(p);
	auto dist = [&](pi a, pi b){
		return hypot(b.first - a.first, b.second - a.second);
	};
	int pt = 0;
	for(int i=0; i<p.size(); i++){
		while(pt+1 < p.size() && dist(p[i], p[pt]) <= dist(p[i], p[pt+1])) pt++;
		if(dist(p[i], p[pt]) >= 2 * d) return 1;
	}
	return 0;
}
   
int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&x[i],&y[i]);
	}
	x[n] = x[0], y[n] = y[0];
	for(int i=0; i<n; i++){
		int a = y[i] - y[i+1];
		int b = x[i+1] - x[i];
		v[i] = {1.0 * a, 1.0 * b, - 1.0 * a * x[i] - 1.0 * b * y[i]}; 
	}
	double s = 0, e = 1e7;
	for(int i=0; i<50; i++){
		double m = (s+e)/2;
		if(trial(m)) s = m;
		else e = m;
	}
	printf("%.3f",s);
}

Compilation message (stderr)

2circles.cpp: In function 'void get_points(std::vector<std::pair<long double, long double> >&, double)':
2circles.cpp:96:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<dq.size()-1; i++){
                ^
2circles.cpp: In function 'bool trial(double)':
2circles.cpp:126:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<p.size(); i++){
                ^
2circles.cpp:127:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pt+1 < p.size() && dist(p[i], p[pt]) <= dist(p[i], p[pt+1])) pt++;
              ^
2circles.cpp: In function 'int main()':
2circles.cpp:134:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
2circles.cpp:136:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x[i],&y[i]);
                             ^

• Subtask 1: 90 / 100