Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // NgJaBach: Forever Meadow <3
- #include<bits/stdc++.h>
- using namespace std;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- typedef long long int ll;
- typedef unsigned long long ull;
- #define pb push_back
- #define pob pop_back
- #define mp make_pair
- #define upb upper_bound
- #define lwb lower_bound
- #define bend(a) a.begin(),a.end()
- #define rev(x) reverse(bend(x))
- #define mset(a) memset(a, 0, sizeof(a))
- #define fi first
- #define se second
- #define gcd __gcd
- #define getl(s) getline(cin, s);
- #define setpre(x) fixed << setprecision(x)
- #define endl '\n'
- const int N=1050,M=1000000007;
- const ll INF=1e18+7;
- struct point{
- int x,y;
- void input(){
- cin>>x>>y;
- return;
- }
- }gay[N];
- bool sexy(point A,point B){
- if(A.x==B.x) return A.y<B.y;
- return A.x<B.x;
- }
- int cross_product(point u,point v){
- return u.x*v.y-u.y*v.x;
- }
- int determine_convexhull(point A,point B,point C){ // A <-- B --> C
- point BA,BC;
- BA.x=A.x-B.x;
- BA.y=A.y-B.y;
- BC.x=C.x-B.x;
- BC.y=C.y-B.y;
- return cross_product(BA,BC);
- }
- double dist(point A,point B){
- double x,y;
- x=A.x-B.x; y=A.y-B.y;
- return sqrt(x*x+y*y);
- }
- double polygon_area(vector<point>vec){
- vec.pb(vec[0]);
- double sum=0,two=2;
- for(int i=1;i<vec.size();++i){
- sum+=(double)cross_product(vec[i-1],vec[i]);
- }
- sum/=two;
- return abs(sum);
- }
- double polygon_perimeter(vector<point>vec){
- vec.pb(vec[0]);
- double sum=0;
- for(int i=1;i<vec.size();++i){
- sum+=dist(vec[i-1],vec[i]);
- }
- return sum;
- }
- int main(){
- ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
- // freopen("BAOLOI.inp","r",stdin);
- // freopen("BAOLOI.out","w",stdout);
- int n,m;
- cin>>n;
- for(int i=1;i<=n;++i) gay[i].input();
- sort(gay+1,gay+n+1,sexy);
- vector<point>up,down,res;
- point Lp,Rp;
- up.pb(gay[1]); down.pb(gay[1]);
- Lp=gay[1]; Rp=gay[n];
- for(int i=2;i<=n;++i){
- if(i==n or (determine_convexhull(Lp,gay[i],Rp)<0)){
- while(up.size()>=2 and !(determine_convexhull(up[up.size()-2],up[up.size()-1],gay[i])<0)) up.pob();
- up.pb(gay[i]);
- }
- if(i==n or (determine_convexhull(Lp,gay[i],Rp)>0)){
- while(down.size()>=2 and !(determine_convexhull(down[down.size()-2],down[down.size()-1],gay[i])>0)) down.pob();
- down.pb(gay[i]);
- }
- }
- m=up.size();
- for(int i=0;i<m;++i) res.pb(up[i]);
- m=down.size();
- for(int i=m-2;i>0;--i) res.pb(down[i]);
- // for(auto tmp:res) cout<<tmp.x<<" "<<tmp.y<<endl;
- cout<<res.size()<<endl;
- cout<<setpre(3)<<polygon_perimeter(res)<<endl<<polygon_area(res);
- return 0;
- }
- /*
- ==================================+
- INPUT: |
- ------------------------------ |
- 8
- 7 1
- 16 2
- 1 5
- 13 8
- 11 9
- 5 10
- 2 8
- 7 5
- ------------------------------ |
- ==================================+
- OUTPUT: |
- ------------------------------ |
- ------------------------------ |
- ==================================+
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement