Advertisement
NgJaBach

Geometry

Aug 14th, 2022
741
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.90 KB | None | 0 0
  1. // NgJaBach: Forever Meadow <3
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  7. typedef long long int ll;
  8. typedef unsigned long long ull;
  9. #define pb push_back
  10. #define pob pop_back
  11. #define mp make_pair
  12. #define upb upper_bound
  13. #define lwb lower_bound
  14. #define bend(a) a.begin(),a.end()
  15. #define rev(x) reverse(bend(x))
  16. #define mset(a) memset(a, 0, sizeof(a))
  17. #define fi first
  18. #define se second
  19. #define gcd __gcd
  20. #define getl(s) getline(cin, s);
  21. #define setpre(x) fixed << setprecision(x)
  22. #define endl '\n'
  23. const int N=1050,M=1000000007;
  24. const ll INF=1e18+7;
  25. struct point{
  26.     int x,y;
  27.     void input(){
  28.         cin>>x>>y;
  29.         return;
  30.     }
  31. }gay[N];
  32. bool sexy(point A,point B){
  33.     if(A.x==B.x) return A.y<B.y;
  34.     return A.x<B.x;
  35. }
  36. int cross_product(point u,point v){
  37.     return u.x*v.y-u.y*v.x;
  38. }
  39. int determine_convexhull(point A,point B,point C){ // A <-- B --> C
  40.     point BA,BC;
  41.     BA.x=A.x-B.x;
  42.     BA.y=A.y-B.y;
  43.     BC.x=C.x-B.x;
  44.     BC.y=C.y-B.y;
  45.     return cross_product(BA,BC);
  46. }
  47. double dist(point A,point B){
  48.     double x,y;
  49.     x=A.x-B.x; y=A.y-B.y;
  50.     return sqrt(x*x+y*y);
  51. }
  52. double polygon_area(vector<point>vec){
  53.     vec.pb(vec[0]);
  54.     double sum=0,two=2;
  55.     for(int i=1;i<vec.size();++i){
  56.         sum+=(double)cross_product(vec[i-1],vec[i]);
  57.     }
  58.     sum/=two;
  59.     return abs(sum);
  60. }
  61. double polygon_perimeter(vector<point>vec){
  62.     vec.pb(vec[0]);
  63.     double sum=0;
  64.     for(int i=1;i<vec.size();++i){
  65.         sum+=dist(vec[i-1],vec[i]);
  66.     }
  67.     return sum;
  68. }
  69. int main(){
  70.     ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
  71. //    freopen("BAOLOI.inp","r",stdin);
  72. //    freopen("BAOLOI.out","w",stdout);
  73.     int n,m;
  74.     cin>>n;
  75.     for(int i=1;i<=n;++i) gay[i].input();
  76.     sort(gay+1,gay+n+1,sexy);
  77.     vector<point>up,down,res;
  78.     point Lp,Rp;
  79.     up.pb(gay[1]); down.pb(gay[1]);
  80.     Lp=gay[1]; Rp=gay[n];
  81.     for(int i=2;i<=n;++i){
  82.         if(i==n or (determine_convexhull(Lp,gay[i],Rp)<0)){
  83.             while(up.size()>=2 and !(determine_convexhull(up[up.size()-2],up[up.size()-1],gay[i])<0)) up.pob();
  84.             up.pb(gay[i]);
  85.         }
  86.         if(i==n or (determine_convexhull(Lp,gay[i],Rp)>0)){
  87.             while(down.size()>=2 and !(determine_convexhull(down[down.size()-2],down[down.size()-1],gay[i])>0)) down.pob();
  88.             down.pb(gay[i]);
  89.         }
  90.     }
  91.     m=up.size();
  92.     for(int i=0;i<m;++i) res.pb(up[i]);
  93.     m=down.size();
  94.     for(int i=m-2;i>0;--i) res.pb(down[i]);
  95. //  for(auto tmp:res) cout<<tmp.x<<" "<<tmp.y<<endl;
  96.     cout<<res.size()<<endl;
  97.     cout<<setpre(3)<<polygon_perimeter(res)<<endl<<polygon_area(res);
  98.     return 0;
  99. }
  100. /*
  101. ==================================+
  102. INPUT:                            |
  103. ------------------------------    |
  104. 8
  105. 7 1
  106. 16 2
  107. 1 5
  108. 13 8
  109. 11 9
  110. 5 10
  111. 2 8
  112. 7 5
  113. ------------------------------    |
  114. ==================================+
  115. OUTPUT:                           |
  116. ------------------------------    |
  117.  
  118. ------------------------------    |
  119. ==================================+
  120. */
  121.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement