Pagini recente » Cod sursa (job #3249593) | Cod sursa (job #44013) | Cod sursa (job #701483) | Cod sursa (job #2580220) | Cod sursa (job #2978861)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std ;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<double,double> Point;
Point Points[120005], S[120005];
int n;
int head ;
void ReadFile()
{
fin >> n ;
for(int i = 1; i <= n ;++i)
{
fin >> Points[i].x >> Points[i].y;
}
}
inline double Prod_Incrucisat(const Point& A, const Point& B, const Point& C )
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int cmp(const Point& P1,const Point& P2)
{
return (Prod_Incrucisat(Points[1], P1, P2) < 0);
}
void Sortare()
{
int pos = 1;
for(int i = 2; i<= n; ++i)
if(Points[i] < Points[pos])
pos = i;
swap(Points[1], Points[pos]);
sort(Points+2, Points+n+1, cmp);
}
void ScanareGraham()
{
Sortare();
S[1] = Points[1];
S[2] = Points[2];
head = 2;
for(int i = 3; i <= n ; ++i)
{
while(head >= 2 && Prod_Incrucisat(S[head-1], S[head], Points[i]) > 0)
--head;
S[++head] = Points[i];
}
}
void Afisare()
{
fout << fixed ;
fout << head << '\n';
for(int i = head ; i>=1; i--)
fout << setprecision(9) << S[i].x << ' ' << S[i].y << '\n';
}
int main()
{
ReadFile();
ScanareGraham();
Afisare();
return 0;
}