fork download
copy 
  1. #include<cstring>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<iostream>
  5. #include<cstdio>
  6. #define rep(i,n) for(int i=0;i<n;i++)
  7. #define pb push_back
  8. using namespace std;
  9. namespace Geometry
  10. {
  11.     namespace Data_Struct
  12.     {
  13.         template<int D>
  14.         struct Point
  15.         {
  16.             double X[D];
  17.             void input()
  18.             {
  19.                 rep(i,D)scanf("%lf",X+i);
  20.             }
  21.             void operator=(const Point&a)
  22.             {
  23.                 memcpy(X,a.X,sizeof(double)*D);
  24.             }
  25.             Point&operator+=(const Point&a)
  26.             {
  27.                 rep(i,D)X[i]+=a.X[i];
  28.                 return *this;
  29.             }
  30.             Point&operator-=(const Point&a)
  31.             {
  32.                 rep(i,D)X[i]-=a.X[i];
  33.                 return *this;
  34.             }
  35.             Point&operator*=(double d)
  36.             {
  37.                 rep(i,D)X[i]*=d;
  38.                 return *this;
  39.             }
  40.             Point&operator/=(double d)
  41.             {
  42.                 rep(i,D)X[i]/=d;
  43.                 return *this;
  44.             }
  45.             Point operator+(const Point&a)
  46.             {
  47.                 Point ret=*this;
  48.                 return ret+=a;
  49.             }
  50.             Point operator-(const Point&a)
  51.             {
  52.                 Point ret=*this;
  53.                 return ret-=a;
  54.             }
  55.             Point operator*(double d)
  56.             {
  57.                 Point ret=*this;
  58.                 return ret*=d;
  59.             }
  60.             Point operator/(double d)
  61.             {
  62.                 Point ret=*this;
  63.                 return ret/=d;
  64.             }
  65.             bool operator<(const Point&a)const
  66.             {
  67.                 rep(i,D)
  68.                 {
  69.                     if(X[i]<a.X[i])return true;
  70.                     if(X[i]>a.X[i])return false;
  71.                 }
  72.                 return false;
  73.             }
  74.         };
  75.         typedef Point<1> Point1D;
  76.         typedef Point<2> Point2D;
  77.         typedef Point<3> Point3D;
  78.         double dot(Point2D a,Point2D b)
  79.         {
  80.             return a.X[0]*b.X[0]+a.X[1]*b.X[1];
  81.         }
  82.         double det(Point2D a,Point2D b)
  83.         {
  84.             return a.X[0]*b.X[1]-a.X[1]*b.X[0];
  85.         }
  86.         template<int D>
  87.         struct Rec
  88.         {
  89.             typedef Point<D> PointD;
  90.             PointD low,high;
  91.             void just()
  92.             {
  93.                 rep(i,D)
  94.                 {
  95.                     if(low.X[i]>high.X[i])
  96.                         swap(low.X[i],high.X[i]);
  97.                 }
  98.             }
  99.             bool inrange(double x,double l,double r)
  100.             {
  101.                 return(x>=l&&x<=r);
  102.             }
  103.             bool Contain(const PointD&a)const
  104.             {
  105.                 rep(i,D)
  106.                 {
  107.                     if(!inrange(a.X[i],low.X[i],high.X[i]))
  108.                         return false;
  109.                 }
  110.                 return true;
  111.             }
  112.         };
  113.         typedef Rec<1> Rec1D;
  114.         typedef Rec<2> Rec2D;
  115.         typedef Rec<3> Rec3D;
  116.     }
  117.     namespace Algorithm
  118.     {
  119.         namespace ConvexHull
  120.         {
  121.             typedef Geometry::Data_Struct::Point2D Point;
  122.             using Geometry::Data_Struct::det;
  123.             using Geometry::Data_Struct::dot;
  124.             vector<Point> Calc_ConvexHull(vector<Point> P)
  125.             {
  126.                 sort(P.begin(),P.end());
  127.                 int n=P.size(),k=0;
  128.                 if(n<=1)return P;
  129.                 vector<Point> qs(2*n);
  130.                 for(int i=0;i<n;qs[k++]=P[i++])
  131.                     while(k>1&&det(qs[k-1]-qs[k-2],P[i]-qs[k-1])<=0)k--;
  132.                 for(int i=n-2,t=k;i>=0;qs[k++]=P[i--])
  133.                     while(k>t&&det(qs[k-1]-qs[k-2],P[i]-qs[k-1])<=0)k--;
  134.                 vector<Point> ret(qs.begin(),qs.begin()+k);
  135.                 return ret;
  136.             }
  137.             double Area(const vector<Point>&P)
  138.             {
  139.                 int n=P.size();double ret=0;
  140.                 rep(i,n)ret+=det(P[i],P[(i+1)%n]);
  141.                 return ret/2;
  142.             }
  143.         }
  144.     }
  145. }
  146. int main()
  147. {
  148.     using namespace Geometry::Algorithm::ConvexHull;
  149.     vector<Point> A;
  150.     rep(i,4)
  151.     {
  152.         Point a;a.input();
  153.         A.pb(a);
  154.     }
  155.     vector<Point>ret=Calc_ConvexHull(A);
  156.     cout<<Area(ret)<<endl;
  157. }
  158.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bP3MN
language:
C++ (gcc 8.3)
created:
13 years 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!