Pagini recente » Istoria paginii runda/lot2010mixt2 | Cod sursa (job #1141702) | Cod sursa (job #2491062) | Cod sursa (job #2559762) | Cod sursa (job #1989422)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x, y;
};
punct p[120001], st[120001];
int N, H;
void afis()
{
g << H << '\n';
g << fixed << setprecision(6);
for(int i = H; i > 0; i--)
g << st[i].x << ' ' << st[i].y << '\n';
}
void swap(punct &A, punct &B)
{
punct aux;
aux = A;
A = B;
B = aux;
}
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) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x);
}
int compd(const punct &A, const punct &B)
{
return det(p[1], A, B) < 0;
}
int main()
{
f >> N;
int ip0 = 1;
for(int i = 1; i <= N; i++)
{
f >> p[i].x >> p[i].y;
if(compx(p[i], p[ip0]))
ip0 = i;
}
swap(p[ip0], p[1]);
sort(p + 2, p + N + 1, compd);
st[1] = p[1];
st[2] = p[2];
H = 2;
for(int i = 3; i <= N; i++)
{
while(H >= 2 && det(st[H - 1], st[H], p[i]) > 0)
H--;
st[++H] = p[i];
}
afis();
return 0;
}