Pagini recente » Cod sursa (job #1795647) | Cod sursa (job #592769) | Cod sursa (job #1810327) | Cod sursa (job #2871037) | Cod sursa (job #2371478)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 1200002;
vector <int> S;
int N;
struct node
{
double x,y;
}Node[NMAX];
node NOD;
int poz;
void Read()
{
NOD.x=NOD.y=2000000000;
fin>>N;
for(int i=1;i<=N;++i)
{
fin>>Node[i].x>>Node[i].y;
if(Node[i].y<NOD.y){NOD=Node[i];poz=i;}
else if(Node[i].y==NOD.y && Node[i].x<NOD.x){NOD=Node[i];poz=i;}
}
fin.close();
}
int Orientare( node A, node B, node C )
{
return ( 1LL * B.y - A.y ) * ( 1LL * C.x - B.x ) <= ( 1LL * B.x - A.x ) * ( 1LL * C.y - B.y );
}
bool comp(node A,node B)
{
return Orientare(Node[1],A,B);
}
void Do()
{
swap(Node[poz],Node[1]);
sort(Node+2,Node+N+1,comp);
//for(int i=1;i<=N;++i)cout<<Node[i].x<<" "<<Node[i].y<<"\n";
S.push_back( 1 );
S.push_back( 2 );
for(int i=3;i<=N;++i)
{
while( !Orientare(Node[S[S.size()-2]] , Node[S.back()] , Node[i]) )S.pop_back();
S.push_back(i);
}
fout<<S.size()<<"\n";
for(int i=0;i<S.size();++i)
fout<<fixed<<setprecision(6)<<Node[S[i]].x<<" "<<Node[S[i]].y<<"\n";
}
int main()
{
Read();
Do();
return 0;
}