Pagini recente » Cod sursa (job #3149159) | Cod sursa (job #3224158) | Cod sursa (job #85431) | Cod sursa (job #106744) | Cod sursa (job #1568757)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMax = 120000;
pair <double,double> St[NMax + 5];
int N,Vf;
pair <double,double> P[NMax + 5];
void Read()
{
fin>>N;
for(int i = 1; i<=N; i++)
{
double x,y;
fin >> x >> y;
P[i] = make_pair(x,y);
}
}
double Sign(pair<double,double> A,pair<double,double> B,pair<double,double> C)
{
double S = A.first * B.second + B.first*C.second + C.first * A.second - A.second * B.first - B.second * C.first - C.second*A.first;
return S;
}
bool Compare(pair<double,double> A,pair<double,double> B)
{
return ( Sign(P[1], A, B) > 0);
}
void Solve()
{
int PMin = 1;
for(int i = 2; i <= N; i++)
if ( (P[i].second < P[PMin].second) || (P[i].second == P[PMin].second && P[i].first < P[PMin].first))
PMin = i;
swap(P[1],P[PMin]);
sort(P+2,P+N+1,Compare);
St[1] = P[1]; St[2] = P[2]; Vf = 2;
for(int i = 3; i<=N; i++)
{
while (Vf >=2 && Sign(St[Vf-1],St[Vf],P[i]) < 0)
Vf--;
St[++Vf] = P[i];
}
}
void Print()
{
fout<<Vf<<"\n";
for(int i = 1; i<= Vf; i++)
fout<<fixed<<setprecision(9)<<St[i].first<<" "<<St[i].second<<"\n";
}
int main()
{
Read();
Solve();
Print();
return 0;
}