oj.uz

Submission #17296

# Submission time Handle Problem Language Result Execution time Memory
17296 2015-11-18T13:53:42 Z gs14004 2circles (balkan11_2circles) C++14
40 / 100
 4000 ms 3596 KB 
#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<double, double> pi;

int n;
int x[50005], y[50005];

struct line{
	double a, b, c;
}v[50005];

pi rotate(pi a, pi b, double q){
	int dx = a.second - b.second;
	int dy = b.first - a.first;
	double pyth = hypot(dx, dy);
	return pi(b.first + (dx / pyth) * q, b.second + (dy / pyth) * q);
}

pi cross(line p, line q){
	double base = p.a * q.b - p.b * q.a;
	if(fabs(base) < 1e-5) return pi(1e9, 1e9);
	return pi((p.b * q.c - q.b * p.c) / base, (p.c * q.a - q.c * p.a) / base);
}

bool ccw(pi a, pi b, pi c){
	double dx1 = b.first - a.first;
	double dy1 = b.second - a.second;
	double dx2 = c.first - a.first;
	double dy2 = c.second - a.second;
	return dx1 * dy2 > dy1 * dx2;
}

double func(line a, pi b){
	return a.a * b.first + a.b * b.second + a.c;
}

void half_plane_intersect(vector<pi> &ret){
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			pi crs = cross(v[i], v[j]);
			if(fabs(crs.first - 1e9) < 1e-4) continue;
			bool bad = 0;
			for(int k=0; k<n; k++){
				if(func(v[k], crs) < -1e-4){
					bad = 1;
					break;
				}
			}
			if(!bad) ret.push_back(crs);
		}
	}

}

bool trial(double d){
	for(int i=0; i<n; i++){
		int a = y[i] - y[i+1];
		int b = x[i+1] - x[i];
		pi loc = rotate(pi(x[i], y[i]), pi(x[i+1], y[i+1]), d);
		v[i] = {1.0 * a, 1.0 * b, - a * loc.first - b * loc.second}; // ax + by + c >= 0
	}
	vector<pi> points;
	half_plane_intersect(points);
	double ret = 0;
	for(int i=0; i<points.size(); i++){
		for(int j=0; j<i; j++){
			ret = max(ret, hypot(points[j].first - points[i].first, points[j].second - points[i].second));
		}
	}
	return ret >= 2 * d;
}

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];
	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

2circles.cpp: In function 'bool trial(double)':
2circles.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<points.size(); i++){
                ^
2circles.cpp: In function 'int main()':
2circles.cpp:93:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
2circles.cpp:95: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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3596 KB Output is correct
2 Correct 0 ms 3596 KB Output is correct
3 Correct 53 ms 3596 KB Output is correct
4 Correct 126 ms 3596 KB Output is correct
5 Execution timed out 4000 ms 3596 KB Execution timed out
6 Execution timed out 4000 ms 3596 KB Execution timed out
7 Execution timed out 4000 ms 3596 KB Execution timed out
8 Execution timed out 4000 ms 3596 KB Execution timed out
9 Execution timed out 4000 ms 3596 KB Execution timed out
10 Execution timed out 4000 ms 3596 KB Execution timed out