Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <string>
- using std::vector;
- using std::cin;
- using std::cout;
- using std::endl;
- using std::min;
- using std::max;
- using std::fixed;
- struct point {
- point() { }
- point(long double first, long double second) : x_c(first), y_c(second) { }
- long double x_c, y_c;
- };
- struct vec {
- long double x_c, y_c;
- vec() { }
- vec(long double first, long double second) : x_c(first), y_c(second) { }
- vec(point first, point second) : x_c(second.x_c - first.x_c), y_c(second.y_c - first.y_c) { }
- explicit vec(point end) : x_c(end.x_c), y_c(end.y_c) { }
- long double operator ^ (vec second) {
- return x_c * second.y_c - second.x_c * y_c;
- }
- long double operator * (vec second) {
- return x_c * second.x_c + y_c * second.y_c;
- }
- long double len() {
- return sqrt(x_c * x_c + y_c * y_c);
- }
- };
- struct line {
- line() { }
- line(point start, vec direction) : begin(start), dir(direction) { }
- line(point first_point, point second_point) :
- begin(first_point), dir(vec(first_point, second_point)) { }
- point begin;
- vec dir;
- };
- long double square(const vector<point>& polygon) {
- if (polygon.size() < 3)
- return 0;
- long double area = 0;
- for (size_t i = 1; i < polygon.size() - 1; ++i) {
- area += vec(polygon[0], polygon[i]) ^ vec(polygon[0], polygon[i + 1]);
- }
- return abs(area) / 2;
- }
- const long double INF = 1e15;
- const long double EPS = 1e-10;
- const long double PI = atan2(0, -1);
- vector<point> points;
- point intersect(line first_line, line second_line) {
- long double tmp = (vec(first_line.begin, second_line.begin) ^ second_line.dir)
- / (first_line.dir ^ second_line.dir);
- return point(first_line.begin.x_c + tmp * first_line.dir.x_c,
- first_line.begin.y_c + tmp * first_line.dir.y_c);
- }
- void divide(const vector<point>& points, line delim, vector<point>& left, vector<point>& right) {
- left.clear();
- right.clear();
- for (size_t it = 0; it < points.size(); ++it) {
- if ((vec(delim.begin, points[it]) ^ delim.dir) < 0)
- left.push_back(points[it]);
- else
- right.push_back(points[it]);
- point first_point = points[it];
- point second_point;
- if (it + 1 == points.size())
- second_point = points[0];
- else
- second_point = points[it + 1];
- point inter = intersect(delim, line(first_point, second_point));
- if (vec(inter, first_point) * vec(inter, second_point) <= 0) {
- left.push_back(inter);
- right.push_back(inter);
- }
- }
- }
- line find_line(vec dir) {
- long double len = dir.len();
- dir.x_c /= len;
- dir.y_c /= len;
- vec norm(dir.y_c, -dir.x_c);
- long double left = INF, right = -INF;
- for (size_t i = 0; i < points.size(); ++i) {
- left = min(left, vec(points[i]) * norm);
- right = max(right, vec(points[i]) * norm);
- }
- while (right - left > EPS) {
- long double mid = (left + right) / 2;
- line delim(point(norm.x_c * mid, norm.y_c * mid), dir);
- vector<point> first_part, second_part;
- divide(points, delim, first_part, second_part);
- if (square(first_part) - square(second_part) < 0)
- left = mid;
- else
- right = mid;
- }
- long double mid = (left + right) / 2;
- return line(point(norm.x_c * mid, norm.y_c * mid), dir);
- }
- int main() {
- int number;
- cin >> number;
- points.resize(number);
- for (int i = 0; i < number; ++i) {
- cin >> points[i].x_c >> points[i].y_c;
- }
- long double left = 0, right = PI / 2;
- while (right - left > EPS) {
- long double mid = (left + right) / 2;
- vector<point> first_part, second_part, third_part, fourth_part;
- line first_delim = find_line(vec(sin(mid), cos(mid)));
- line second_delim = find_line(vec(cos(mid), -sin(mid)));
- divide(points, first_delim, first_part, second_part);
- divide(first_part, second_delim, third_part, fourth_part);
- if (square(third_part) - square(fourth_part) < 0)
- left = mid;
- else
- right = mid;
- }
- long double mid = (left + right) / 2;
- line first_delim = find_line(vec(sin(mid), cos(mid)));
- line second_delim = find_line(vec(cos(mid), -sin(mid)));
- point ans = intersect(first_delim, second_delim);
- cout.precision(10);
- cout << fixed;
- cout << ans.x_c << ' ' << ans.y_c << endl << 180 * mid / PI;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement