Pagini recente » Cod sursa (job #1650901) | Rating Carina Maria Viespescu (puficarina) | Cod sursa (job #1641957) | Cod sursa (job #526579) | Cod sursa (job #2371412)
#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)
{
long long o1=(A.y-B.y)*(B.x-C.x);
long long o2=(A.x-B.x)*(B.y-C.y);
if(o1==o2)return 0;
if(o1>o2)return -1;
return 1;
}
bool comp(node A,node B)
{
return (Orientare(Node[1],A,B)>=0);
}
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])==-1 )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;
}