Pagini recente » Cod sursa (job #94277) | Cod sursa (job #1485539) | Cod sursa (job #1449324) | Cod sursa (job #2882528) | Cod sursa (job #2139468)
#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) * (B.y - C.y) - (A.y - B.y) * (B.x - C.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]) < EPS)
{
viz[st[H]] = 0;
H--;
}
st[++H] = i;
viz[i] = 1;
if(i == N)
k = -1;
}
H--;
afis();
return 0;
}