Pagini recente » Cod sursa (job #866792) | Cod sursa (job #1669847) | Cod sursa (job #1853656) | Cod sursa (job #485466) | Cod sursa (job #1877604)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMax = 120005;
int N,NStack;
int Stack[NMax];
pair < double, double > P [NMax];
int Sign(pair < double, double> A, pair < double, double >B, pair <double, double> C)
{
return A.first * B.second + B.first * C.second + C.first * A.second - A.second * B.first - B.second * C.first - C.second * A.first;
}
bool Compare( pair < double, double> A, pair < double, double >B)
{
return Sign(P[1],A,B) > 0;
}
void Read()
{
fin >> N;
for(int i = 1; i <= N; ++i)
{
double x,y;
fin >> x >> y;
P[i] = make_pair(x,y);
}
int Min = 1;
for(int i = 2; i <= N; ++i)
{
if(P[i].second < P[Min].second || (P[i].second == P[Min].second && P[i].first < P[Min].first) )
Min = i;
}
swap(P[1],P[Min]);
sort(P + 2, P + N + 1,Compare);
}
void Solve()
{
Stack[1] = 1; Stack[2] = 2;
NStack = 2;
for(int i = 3; i <= N; ++i)
{
while(NStack > 2 && Sign(P[Stack[NStack - 1]],P[Stack[NStack]], P[i] ) < 0)
NStack--;
Stack[++NStack] = i;
}
}
void Print()
{
fout << NStack << "\n";
for(int i = 1; i <= NStack; ++i)
fout << fixed << setprecision(6)<< P[Stack[i]].first << " " << P[Stack[i]].second << "\n";
}
int main()
{
Read();
Solve();
Print();
return 0;
}