Pagini recente » Cod sursa (job #2782795) | Cod sursa (job #1751717) | Cod sursa (job #1411343) | Cod sursa (job #1597711) | Cod sursa (job #2139451)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
//const double EPS=1e-12;
struct punct
{
double x, y;
};
punct p[120001];
int st[120001];
bool viz[120001];
int N, H;
void afis()
{
g << H << '\n';
g << fixed << setprecision(6);
for(int i = 1; i <= H; i++)
g << p[st[i]].x << ' ' << p[st[i]].y << '\n';
}
int compx(const punct &A, const punct &B)
{
if(A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
double det(const punct &A, const punct &B, const punct &C)
{
return (A.x - B.x) * (C.y - A.y) - (A.y - B.y) * (C.x - A.x);
}
int main()
{
f >> N;
for(int i = 1; i <= N; i++)
f >> p[i].x >> p[i].y;
sort(p + 1, p + N + 1, compx);
st[1] = 1;
st[2] = 2;
viz[2] = 1;
H = 2;
for(int i = 3, k = 1; i >= 1; i += k)
{
if(viz[i] == 1)
continue;
while(H >= 2 && det(p[st[H - 1]], p[st[H]], p[i]) < 0)
{
viz[st[H]] = 0;
H--;
}
st[++H] = i;
viz[i]=1;
if(i == N)
k = -1;
}
H--;
afis();
return 0;
}