fork download
copy 
  1. // i wants to take ioi
  2. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define int long long
  8. #define nn "\n"
  9. #define pi pair<int, int>
  10. #define fi first
  11. #define se second
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define eb emplace_back
  15. #define pb push_back
  16. #define TASK "Haidoanthang"
  17.  
  18. #define ms(a, x) memset(a, x, sizeof(a))
  19. #define all(a) a.begin(), a.end()
  20. #define All(a, n) a + 1, a + 1 + n
  21.  
  22. #define LOG 19
  23.  
  24. const int INF = 1e18;
  25. const int mod = 1e9;
  26. const int N = 1e5 + 5;
  27. const int MOD = 998244353;
  28. struct Point{
  29.     int x, y;
  30. };
  31. int n;
  32. vector<Point> p;
  33. int ccw(Point a, Point b, Point c){
  34.     int val = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  35.     if(val == 0) return 0;
  36.     return (val > 0) ? 1 : -1;
  37. }
  38. bool onSegment(Point p, Point a, Point b){
  39.     return p.x >= min(a.x, b.x) && p.x <= max(a.x, b.x) && p.y >= min(a.y, b.y) && p.y <= max(a.y, b.y);
  40. }
  41. bool intersect(Point a, Point b, Point c, Point d){
  42.     int d1 = ccw(a, b, c);
  43.     int d2 = ccw(a, b, d);
  44.     int d3 = ccw(c, d, a);
  45.     int d4 = ccw(c, d, b);
  46.     if(((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return 1;
  47.     return 0;
  48. }
  49. bool pointOnSegmentStrict(Point p, Point a, Point b) {
  50.     if(ccw(a, b, p) != 0) return false;
  51.     return (p.x > min(a.x, b.x) && p.x < max(a.x, b.x)) || (p.y > min(a.y, b.y) && p.y < max(a.y, b.y));
  52. }
  53. void nhap() {
  54.     cin >> n;
  55.     p.resize(n);
  56.     for(int i = 0; i < n; i++){
  57.         cin >> p[i].x >> p[i].y;
  58.     }
  59. }
  60. void solve() {
  61.     bool oke = 0;
  62.     for(int i = 0; i < n; ++i){
  63.         int next_i = (i + 1) % n;
  64.         for(int j = i + 1; j < n; ++j){
  65.             int next_j = (j + 1) % n;
  66.             if (i == j || next_i == j || next_j == i) continue;
  67.             if (intersect(p[i], p[next_i], p[j], p[next_j])){
  68.                 oke = 1;
  69.                 break;
  70.             }
  71.         }
  72.         if(oke) break;
  73.     }
  74.     if(!oke){
  75.         for(int i = 0; i < n; ++i){
  76.             int next_i = (i + 1) % n;
  77.             for(int j = 0; j < n; ++j){
  78.                 if(j == i || j == next_i) continue;
  79.                 if(pointOnSegmentStrict(p[j], p[i], p[next_i])){
  80.                     oke = 1;
  81.                     break;
  82.                 }
  83.             }
  84.             if(oke) break;
  85.         }
  86.     }
  87.     if(oke){
  88.         cout << 3 << nn;
  89.         cout << 0 << nn;
  90.         return;
  91.     }
  92.     bool has_pos = false, has_neg = false;
  93.     for(int i = 0; i < n; i++){
  94.         Point a = p[i];
  95.         Point b = p[(i + 1) % n];
  96.         Point c = p[(i + 2) % n];
  97.         int dir = ccw(a, b, c);
  98.         if (dir > 0) has_pos = true;
  99.         if (dir < 0) has_neg = true;
  100.     }
  101.     int polygon_type = 1;
  102.     if(has_pos && has_neg){
  103.         polygon_type = 2;
  104.     }
  105.     int double_area = 0;
  106.     for(int i = 0; i < n; ++i){
  107.         int j = (i + 1) % n;
  108.         double_area += (p[i].x * p[j].y - p[j].x * p[i].y);
  109.     }
  110.     double area = abs(double_area) / 2.0;
  111.     cout << polygon_type << nn;
  112.     cout << fixed << setprecision(3) << area << nn;
  113. }
  114. signed main() {
  115.     if (fopen(TASK".inp", "r")) {
  116.         freopen(TASK".inp", "r", stdin);
  117.         freopen(TASK".out", "w", stdout);
  118.     }
  119.     ios_base::sync_with_stdio(0);
  120.     cin.tie(0);
  121.     cout.tie(0);
  122.     nhap();
  123.     solve();
  124.     return (0 ^ 0);
  125. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
4
0 0
0 5
5 5
5 0
stdout
copy 
1
25.000
https://ideone.com/TbygJE
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!