Pagini recente » Cod sursa (job #2062811) | Cod sursa (job #57186) | Cod sursa (job #754460) | Cod sursa (job #1174250) | Cod sursa (job #2371447)
#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();
}
bool Orientare(node A,node B,node C)
{
long long o1=1LL*((A.y-B.y)*(B.x-C.x));
long long o2=1LL*((A.x-B.x)*(B.y-C.y));
return o1<=o2;
}
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 );
S.push_back( 3 );
for(int i=4;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;
}