Pagini recente » Cod sursa (job #179200) | Cod sursa (job #1907128) | Clasament preONI 2007, Runda 2, Clasele 11-12 | Cod sursa (job #1608347) | Cod sursa (job #963649)
Cod sursa(job #963649)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Point
{
double x, y;
};
Point vp[120005], st[120005];
int N;
double x_prod(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);
}
bool cmp(const Point& p1, const Point& p2)
{
return x_prod(vp[0], p1, p2) > 0;
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in >> N;
for(int i = 0; i < N; ++i)
{
in >> vp[i].x >> vp[i].y;
}
int minp = 0;
for(int i = 1; i < N; ++i)
{
if((vp[i].y < vp[minp].y) || (vp[i].y == vp[minp].y && vp[i].x < vp[minp].x))
{
minp = i;
}
}
swap(vp[0], vp[minp]);
sort(vp + 1, vp + N, cmp);
st[0] = vp[0];
st[1] = vp[1];
int last = 1;
for(int i = 2; i < N; ++i)
{
while(last >= 1 && x_prod(st[last - 1], st[last], vp[i]) < 0)
--last;
st[++last] = vp[i];
}
out << last + 1 << endl;
out << fixed;
out << setprecision(6) << st[0].x << " " << st[0].y << endl;
for(int i = 1; i <= last; ++i)
{
out << setprecision(6) << st[i].x << " " << st[i].y << endl;
}
return 0;
}