include iostream include vector include cmath include iomanip using na

  • Anonymous
  • Text only
  • 11 Apr 2014 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>

#include <vector>

#include <cmath>

#include <iomanip>

using namespace std;

const double eps = 1e-8;

struct pt

{

	double x;

	double y;

	pt(double X = 0, double Y = 0): x(X), y(Y){};

};

pt operator+(pt a, pt b)

{

	return pt(a.x + b.x, a.y + b.y);

}

pt operator-(pt a, pt b)

{

	return pt(a.x - b.x, a.y - b.y);

}

pt operator*(pt a, double v)

{

	return pt(a.x * v, a.y * v);

}

double sqrLen(pt a)

{

	return a.x * a.x + a.y * a.y;

}

double len(pt a)

{

	return sqrt(sqrLen(a));

}

double dot(pt a, pt b)

{

	return a.x * b.x + a.y * b.y;

}

double cross(pt a, pt b)

{

	return a.x * b.y - a.y * b.x;

}

bool check_intersect(pt c1, pt c2, double r)

{

	return (sqrLen(c1 - c2) <= 4 * r * r + eps);

}

pt normalize(pt a)

{

	double length = len(a);

	return pt(a.x / length, a.y / length);

}

pair<pt, pt> rotate(pt a, double cos_alfa, double sin_alfa)

{

	pair<pt, pt> ans;

	ans.first = pt (a.x * cos_alfa + a.y * sin_alfa, -sin_alfa * a.x + cos_alfa * a.y);

	ans.second = pt (a.x * cos_alfa - a.y * sin_alfa, sin_alfa * a.x + cos_alfa * a.y);

	return ans;

}

pair<pt, pt> intersect_circles(pt c1, pt c2, double r)

{

	pair<pt, pt> ans;

	pt v1 = c2 - c1;

	double cos_alfa = len(v1) / (2 * r);

	double sin_alfa = sqrt(1 - cos_alfa * cos_alfa);

	pt v_norm_r = normalize(v1) * r;

	pair<pt, pt> rot_rez = rotate(v_norm_r, cos_alfa, sin_alfa);

	ans.first = c1 + rot_rez.first;

	ans.second = c1 + rot_rez.second;

	return ans;

}

pair<pt, pt> intersect_circle_and_city(pt c1, double r_pos, double r_city)

{



}

void find_intersect_points(double r, vector<pt>& plants)

{



}

bool check_blanks(vector<pt>& plants, double r_pos, double r_city)

{

	for (int i = 0; i < plants.size(); ++i)

        if (r_pos > r_city && (r_city - r_pos) * (r_city - r_pos)>= sqrLen(plants[i]))

            return false;

	if (plants.size() == 1)

		return true;



}

void bin_search(double& r_left, double& r_right, double r_city, vector<pt>& plants)

{

	double r_mid = (r_left + r_right) / 2;

	if (){

		r_left = r_mid;

		bin_search(r_left, r_right, r_city, plants);

	}

	else{

		r_right = r_mid;

		bin_search(r_left, r_right, r_city, plants);

	}

}

double solve(int n, double r_city)

{

	double ans_r = 1e4;

	vector<pt> plants(n);

	for (int i = 0; i < n; i++)

		cin >> plants[i].x >> plants[i].y;

	double r_left = 0;

	double r_right = 2 * 1e3 + 1;

	bin_search(r_left, r_right, r_city, plants);

	return ans_r;

}

int main()

{

	ios_base::sync_with_stdio(false);

	int n, r;

	cout << setprecision(6) << fixed << solve(n, r) << endl;



	return 0;

}
← newer dump
older dump →