Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <set>
  7. #include <string>
  8.  
  9. using std::vector;
  10. using std::cin;
  11. using std::cout;
  12. using std::endl;
  13. using std::min;
  14. using std::max;
  15. using std::fixed;
  16.  
  17. struct point {
  18.     point() { }
  19.     point(long double first, long double second) : x_c(first), y_c(second) { }
  20.     long double x_c, y_c;
  21. };
  22.  
  23. struct vec {
  24.    
  25.     long double x_c, y_c;
  26.    
  27.     vec() { }
  28.     vec(long double first, long double second) : x_c(first), y_c(second) { }
  29.     vec(point first, point second) : x_c(second.x_c - first.x_c), y_c(second.y_c - first.y_c) { }
  30.     explicit vec(point end) : x_c(end.x_c), y_c(end.y_c) { }
  31.    
  32.     long double operator ^ (vec second) {
  33.         return x_c * second.y_c - second.x_c * y_c;
  34.     }
  35.     long double operator * (vec second) {
  36.         return x_c * second.x_c + y_c * second.y_c;
  37.     }
  38.    
  39.     long double len() {
  40.         return sqrt(x_c * x_c + y_c * y_c);
  41.     }
  42. };
  43.  
  44. struct line {
  45.     line() { }
  46.     line(point start, vec direction) : begin(start), dir(direction) { }
  47.     line(point first_point, point second_point) :
  48.         begin(first_point), dir(vec(first_point, second_point)) { }
  49.     point begin;
  50.     vec dir;
  51. };
  52.  
  53. long double square(const vector<point>& polygon) {
  54.     if (polygon.size() < 3)
  55.         return 0;
  56.     long double area = 0;
  57.     for (size_t i = 1; i < polygon.size() - 1; ++i) {
  58.        area += vec(polygon[0], polygon[i]) ^ vec(polygon[0], polygon[i + 1]);
  59.     }
  60.     return abs(area) / 2;
  61. }
  62.  
  63. const long double INF = 1e15;
  64. const long double EPS = 1e-10;
  65. const long double PI = atan2(0, -1);
  66.  
  67. vector<point> points;
  68.  
  69. point intersect(line first_line, line second_line) {
  70.     long double tmp = (vec(first_line.begin, second_line.begin) ^ second_line.dir)
  71.                         / (first_line.dir ^ second_line.dir);
  72.     return point(first_line.begin.x_c + tmp * first_line.dir.x_c,
  73.                  first_line.begin.y_c + tmp * first_line.dir.y_c);
  74. }
  75.  
  76. void divide(const vector<point>& points, line delim, vector<point>& left, vector<point>& right) {
  77.     left.clear();
  78.     right.clear();
  79.  
  80.     for (size_t it = 0; it < points.size(); ++it) {
  81.         if ((vec(delim.begin, points[it]) ^ delim.dir) < 0)
  82.             left.push_back(points[it]);
  83.         else
  84.             right.push_back(points[it]);
  85.        
  86.         point first_point = points[it];
  87.         point second_point;
  88.         if (it + 1 == points.size())
  89.             second_point = points[0];
  90.         else
  91.             second_point = points[it + 1];
  92.  
  93.         point inter = intersect(delim, line(first_point, second_point));
  94.         if (vec(inter, first_point) * vec(inter, second_point) <= 0) {
  95.             left.push_back(inter);
  96.             right.push_back(inter);
  97.         }
  98.     }
  99. }
  100.  
  101. line find_line(vec dir) {
  102.     long double len = dir.len();
  103.     dir.x_c /= len;
  104.     dir.y_c /= len;
  105.  
  106.     vec norm(dir.y_c, -dir.x_c);
  107.  
  108.     long double left = INF, right = -INF;
  109.     for (size_t i = 0; i < points.size(); ++i) {
  110.         left = min(left, vec(points[i]) * norm);
  111.         right = max(right, vec(points[i]) * norm);
  112.     }
  113.  
  114.     while (right - left > EPS) {
  115.         long double mid = (left + right) / 2;
  116.  
  117.         line delim(point(norm.x_c * mid, norm.y_c * mid), dir);
  118.  
  119.         vector<point> first_part, second_part;
  120.         divide(points, delim, first_part, second_part);
  121.  
  122.         if (square(first_part) - square(second_part) < 0)
  123.             left = mid;
  124.         else
  125.             right = mid;
  126.     }
  127.  
  128.     long double mid = (left + right) / 2;
  129.     return line(point(norm.x_c * mid, norm.y_c * mid), dir);
  130. }
  131.  
  132. int main() {
  133.  
  134.     int number;
  135.     cin >> number;
  136.  
  137.     points.resize(number);
  138.     for (int i = 0; i < number; ++i) {
  139.         cin >> points[i].x_c >> points[i].y_c;
  140.     }
  141.  
  142.     long double left = 0, right = PI / 2;
  143.     while (right - left > EPS) {
  144.         long double mid = (left + right) / 2;
  145.  
  146.         vector<point> first_part, second_part, third_part, fourth_part;
  147.         line first_delim = find_line(vec(sin(mid), cos(mid)));
  148.         line second_delim = find_line(vec(cos(mid), -sin(mid)));
  149.  
  150.         divide(points, first_delim, first_part, second_part);
  151.         divide(first_part, second_delim, third_part, fourth_part);
  152.  
  153.         if (square(third_part) - square(fourth_part) < 0)
  154.             left = mid;
  155.         else
  156.             right = mid;
  157.     }
  158.  
  159.     long double mid = (left + right) / 2;
  160.     line first_delim = find_line(vec(sin(mid), cos(mid)));
  161.     line second_delim = find_line(vec(cos(mid), -sin(mid)));
  162.  
  163.     point ans = intersect(first_delim, second_delim);
  164.     cout.precision(10);
  165.     cout << fixed;
  166.     cout << ans.x_c << ' ' << ans.y_c << endl << 180 * mid / PI;
  167.  
  168.     return 0;
  169. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement