Cod sursa(job #1420259)

Utilizator azkabancont-vechi azkaban Data 18 aprilie 2015 00:12:29
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-13;
int n;
double a,b;
struct point 
        {
         double x,y;
		} p[120013];
vector < point > St;
struct comp 
      {
     bool operator() (const point &a,const point &b)
        {
         return (a.x<b.x || (a.x==b.x && a.y<b.y));
		}
	  };
	  
int det(point a,point b,point c) 
 {
 return (a.x*b.y - a.y*b.x + 
         b.x*c.y - c.x*b.y + 
		 c.x*a.y - a.x*c.y );
 }

int main(void)
{
 ifstream cin("infasuratoare.in");
 ofstream cout("infasuratoare.out");
 cin>>n;
 for (int i=1;i<=n;++i)
    {
     cin>>a>>b;
     p[i]={a,b};
	}
 sort(p+1,p+n+1,comp());
 St.push_back(p[1]);
 St.push_back(p[2]);
 for (int i=3;i<=n;++i) 
    {
     while (!St.empty() && det(St[St.size()-1],St[St.size()-2],p[i])>0) St.pop_back(); 
     St.push_back(p[i]);
    }
 for (int i=n-1;i>=1;--i) 
    {
     while (!St.empty() && det(St[St.size()-1],St[St.size()-2],p[i])>0) St.pop_back(); 
     St.push_back(p[i]);
    }
 /*
 St.push_back(p[n-1]);
 for (int i=n-2;i>=1;--i) 
    {
     while (!St.empty() && det(St[St.size()-1],St[St.size()-2],p[i])<=0) St.pop_back(); 
     St.push_back(p[i]);
    }*/
 cout<<St.size()<<"\n";
 for (int i=0;i<St.size();++i) cout<<fixed<<setprecision(13)<<St[i].x<<" "<<St[i].y<<"\n";
 return 0;
}