Advertisement
Guest User

asydfgukjasdkasda

a guest
Nov 19th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.02 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define all(x) x.begin(), x.end()
  6. #define endl '\n'
  7. #define sz(x) (int)(x).size()
  8. #define mp(x, y) make_pair(x, y)
  9. #define pb push_back
  10. #define pii pair<int, int>
  11. #define rep(i, f, t) for (auto i = (f); i < (t); ++i)
  12. #define ll long long
  13. #define double long double
  14. #define ull unsigned long long
  15.  
  16. const int inf = (int)(2e9);
  17. const ll INF = (ll)(1e18);
  18. const int MOD = (int)(1e9 + 7);
  19. const double eps = (double)(1e-9);
  20. const double pi = acos(-1);
  21.  
  22. const int maxn = (int)(1e5 + 10);
  23. const int maxm = (int)(2e5 + 10);
  24.  
  25. void solve();
  26.  
  27. template <typename A> inline void print(A x) { cout << x << endl; }
  28. template <typename A, typename B> inline void print(A x, B y) { cout << x << ' ' << y << endl; }
  29. template <typename A, typename B, typename C> inline void print(A x, B y, C z) { cout << x << ' ' << y << ' ' << z << endl; }
  30. template <typename A> inline void in(A &x) { cin >> x; }
  31. template <typename A, typename B> inline void in(A &x, B &y) { cin >> x >> y; }
  32. template <typename A, typename B, typename C> inline void in(A &x, B &y, C &z) { cin >> x >> y >> z; }
  33. template <typename A, typename B, typename C, typename D> inline void in(A &x, B &y, C &z, D &p) { cin >> x >> y >> z >> p; }
  34. template <typename A> inline void read(A begin, A end) { while (begin != end) cin >> *(begin++); }
  35. template <typename A> inline void write(A begin, A end) { while (begin != end) { cout << *(begin++) << ' '; } cout << endl; }
  36.  
  37. ll power(ll a, ll b)
  38. {
  39.     if (b == 0) return 1;
  40.     if (b & 1) return power(a, b - 1) * a;
  41.     ll tmp = power(a, b / 2);
  42.     return tmp * tmp;
  43. }
  44.  
  45. void use_files(string s) {
  46.     freopen(string(s + ".in").c_str(), "r", stdin);
  47.     freopen(string(s + ".out").c_str(), "w", stdout);
  48. }
  49.  
  50. signed main()
  51. {
  52.     std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  53.     srand(time(0));
  54.     cout << fixed << setprecision(20);
  55.     solve();
  56.     return 0;
  57. }
  58.  
  59.  
  60.  
  61. struct Point {
  62.     double x;
  63.     double y;
  64.     Point() {}
  65.     Point(const double& _x, const double& _y) {
  66.         x = _x;
  67.         y = _y;
  68.     }
  69. };
  70. bool operator==(const Point& a, const Point& b) {
  71.     return a.x == b.x && a.y == b.y;
  72. }
  73. double polar_angle(const Point& p) {
  74.     double alpha = atan2(p.y, p.x);
  75.     if (alpha < 0) alpha += 2 * pi;
  76.     return alpha;
  77. }
  78. istream& operator>>(istream& in, Point& p)
  79. {
  80.     in >> p.x >> p.y;
  81.     return in;
  82. }
  83. ostream& operator<<(ostream& out, Point& p) {
  84.     out << p.x << ' ' << p.y;
  85.     return out;
  86. }
  87.  
  88.  
  89.  
  90. struct Vector{
  91.     double x;
  92.     double y;
  93.     Vector() {}
  94.     Vector(const double& _x, const double& _y) {
  95.         x = _x;
  96.         y = _y;
  97.     }
  98.     Vector(const Point& a, const Point& b) {
  99.         x = b.x - a.x;
  100.         y = b.y - a.y;
  101.     }
  102. };
  103. double len(const Vector& a) {
  104.     return sqrt(a.x * a.x + a.y * a.y);
  105. }
  106. double scalar_product(const Vector& a, const Vector& b)
  107. {
  108.     return a.x * b.x + a.y * b.y;
  109. }
  110. double cross_product(const Vector& a, const Vector& b)
  111. {
  112.     return a.x * b.y - b.x * a.y;
  113. }
  114. double alpha(const Vector& a, const Vector& b) {
  115.     return acos(scalar_product(a, b) / (len(a) * len(b)));
  116. }
  117. Vector norm(const Vector& a) {
  118.     Vector res;
  119.     double l = len(a);
  120.     res.x = a.x / l;
  121.     res.y = a.y / l;
  122.     return res;
  123. }
  124.  
  125.  
  126.  
  127. struct Line {
  128.     double a;
  129.     double b;
  130.     double c;
  131.     Line() {}
  132.     Line(const double& _A, const double& _B, const double& _C) {
  133.         a = _A;
  134.         b = _B;
  135.         c = _C;
  136.     }
  137.     Line(const Point& first_point, const Point& second_point) {
  138.         a = second_point.y - first_point.y;
  139.         b = first_point.x - second_point.x;
  140.         c = second_point.x * first_point.y - first_point.x * second_point.y;
  141.     }
  142. };
  143.  
  144. istream& operator>>(istream& in, Line& line) {
  145.     in >> line.a >> line.b >> line.c;
  146.     return in;
  147. }
  148. bool point_in_line(const Point& p, const Line& line) {
  149.     return abs(line.a * p.x + line.b * p.y + line.c) < eps;
  150. }
  151. double dist_to_line_unsigned(const Point& p, const Line& line) {
  152.     return abs(line.a * p.x + line.b * p.y + line.c) / sqrt(line.a * line.a + line.b * line.b);
  153. }
  154. double dist_to_line_signed(const Point& p, const Line& line) {
  155.     return (line.a * p.x + line.b * p.y + line.c) / sqrt(line.a * line.a + line.b * line.b);
  156. }
  157. Point lines_intersection(const Line& first_line, const Line& second_line) {
  158.     Point result;
  159.     double matrix_determinant = (first_line.a * second_line.b - second_line.a * first_line.b);
  160.     result.x = (first_line.b * second_line.c - second_line.b * first_line.c) / matrix_determinant;
  161.     result.y = (first_line.c * second_line.a - second_line.c * first_line.a) / matrix_determinant;
  162.     return result;
  163. }
  164.  
  165.  
  166.  
  167. struct Segment {
  168.     Point a;
  169.     Point b;
  170.     Segment() {}
  171.     Segment(const Point& _a, const Point& _b) {
  172.         a = _a;
  173.         b = _b;
  174.     }
  175. };
  176. istream& operator>>(istream& in, Segment& s) {
  177.     in >> s.a >> s.b;
  178.     return in;
  179. }
  180. double dist_to_segment(const Point& p, const Segment& seg) {
  181.     Vector ab(seg.a, seg.b), ac(seg.a, p), bc(seg.b, p), ba(seg.b, seg.a);
  182.     double result = min(len(ac), len(bc));
  183.     Line line(seg.a, seg.b);
  184.     if ((pi / 2.0) - alpha(ab, ac) > eps && (pi / 2.0) - alpha(bc, ba) > eps)
  185.         result = min(result, dist_to_line_unsigned(p, line));
  186.     return result;
  187. }
  188. bool point_in_segment(const Point& p, const Segment& seg) {
  189.     double length = len(Vector(seg.a, seg.b));
  190.     double len1 = len(Vector(seg.a, p)), len2 = len(Vector(seg.b, p));
  191.     return (abs(length - (len1 + len2)) < eps);
  192. }
  193.  
  194.  
  195.  
  196. struct Polygon {
  197.     vector<Point> poly;
  198.     Polygon(const int& _size) {
  199.         poly.resize(_size);
  200.         for (int i = 0; i < _size; ++i)
  201.             cin >> poly[i];
  202.     }
  203. };
  204. int sign(double x)
  205. {
  206.     if (abs(x) < eps) return 0;
  207.     else if (x < 0) return -1;
  208.     else return 1;
  209. }
  210. Point get_polygon_point(const Polygon& p, const int& index)
  211. {
  212.     return p.poly[index % p.poly.size()];
  213. }
  214. Vector get_polygon_edge(const Polygon& p, const int& index) {
  215.     Vector result(get_polygon_point(p, index), get_polygon_point(p, index + 1));
  216.     return result;
  217. }
  218. bool polygon_is_convex(const Polygon& p)
  219. {
  220.     bool result = true;
  221.     int _sign = 0, i = 0;
  222.     while (i++ < p.poly.size() && _sign == 0)
  223.         _sign = sign(cross_product(get_polygon_edge(p, i), get_polygon_edge(p, i + 1)));
  224.     for (i; i < p.poly.size(); ++i) {
  225.         int t = sign(cross_product(get_polygon_edge(p, i), get_polygon_edge(p, i + 1)));
  226.         result &= (t == _sign || t == 0);
  227.     }
  228.     return result;
  229. }
  230. double orient_angle(const Vector& a, const Vector& b) {
  231.     return alpha(a, b) * sign(cross_product(a, b));
  232. }
  233. bool point_in_polygon(const Point& p, const Polygon& poly)
  234. {
  235.     for (int i = 0; i < poly.poly.size(); ++i)
  236.         if (point_in_segment(p, Segment(get_polygon_point(poly, i), get_polygon_point(poly, i + 1))))
  237.             return true;
  238.     double sum = 0;
  239.     for (int i = 0; i < poly.poly.size(); ++i)
  240.         sum += orient_angle(Vector(p, get_polygon_point(poly, i)), Vector(p, get_polygon_point(poly, i + 1)));
  241.     return (abs(abs(sum) - 2 * pi) < eps);
  242. }
  243. double square_polygon(const Polygon& p)
  244. {
  245.     double result = 0;
  246.     for (int i = 0; i < p.poly.size(); ++i)
  247.         result += (cross_product(Vector(get_polygon_point(p, i + 1), get_polygon_point(p, i)), Vector(get_polygon_point(p, i + 1), get_polygon_point(p, i + 2))) / 2);
  248.     return result;
  249. }
  250.  
  251.  
  252.  
  253. void solve()
  254. {
  255.     int n;
  256.     cin >> n;
  257.     Polygon poly(n);
  258.     print(square_polygon(poly));
  259. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement