Pagini recente » Cod sursa (job #2258542) | Cod sursa (job #2035907) | Cod sursa (job #2550688) | Cod sursa (job #1880527) | Cod sursa (job #1058788)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define in "infasuratoare.in"
#define out "infasuratoare.out"
#define POINT pair < double, double >
#define x first
#define y second
#define Max_Size 120004
std :: ifstream f(in);
std :: ofstream g(out);
int N, Sol[Max_Size];
std :: POINT A[Max_Size];
inline void Read_Data()
{
int poz = 1;
f >> N;
for(int i = 1; i <= N; ++i)
{
f >> A[i].x >> A[i].y;
if(A[i] < A[poz]) poz = i;
}
std :: swap(A[poz], A[1]);
}
inline double det(std :: POINT a, std :: POINT b, std :: POINT c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
struct cmp
{
bool operator () (const std :: POINT &a, const std :: POINT &b)
{
if(det(A[1], a, b) < 0) return 1;
return 0;
};
};
inline void Solve()
{
for(int i = 1; i <= N; ++i)
{
while(Sol[0] >= 2 && det(A[ Sol[ Sol[0] - 1]], A[ Sol[ Sol[0]] ], A[i]) > 0)
Sol[0]--;
Sol[ ++Sol[0] ] = i;
}
}
inline void Write_Data()
{
g << Sol[0] << '\n';
g << std :: fixed << std :: setprecision(6);
for(int i = Sol[0]; i; --i) g << A[ Sol[i] ].x << ' ' << A[ Sol[i] ].y << '\n';
}
int main()
{
Read_Data();
std :: sort (A + 2, A + N + 1, cmp());
Solve();
Write_Data();
//for(int i = 1; i <= N; ++i) g << A[i].x << ' ' << A[i].y << '\n';
return 0;
}