Pagini recente » Istoria paginii runda/still-rockin | Cod sursa (job #2081426) | Cod sursa (job #2463470) | Cod sursa (job #2970683) | Cod sursa (job #940801)
Cod sursa(job #940801)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
struct point
{
double x, y;
bool operator <(const point& a) const{
return (x != a.x? x < a.x : y < a.y);
}
};
bool ccw(point a, point b, point c)
{
return (b.x-a.x)*(c.y-a.y) >= (c.x-a.x)*(b.y-a.y);
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
point p[n];
for (int i = 0; i < n; ++i)
fin >> p[i].x >> p[i].y;
sort(p,p+n);
vector<point> l, u;
for (int i = n-1; i >= 0; --i) {
while (u.size() >= 2)
if (ccw(u[u.size()-2], u.back(), p[i])) break;
else u.pop_back();
u.push_back(p[i]);
}
for (int i = 0; i < n; ++i) {
while (l.size() >= 2)
if (ccw(l[l.size()-2], l.back(), p[i])) break;
else l.pop_back();
l.push_back(p[i]);
}
fout.precision(12);
fout << u.size()+l.size()-2 << '\n';
for (unsigned int i = 1; i < u.size(); ++i)
fout << u[i].x << ' ' << u[i].y << '\n';
for (unsigned int i = 1; i < l.size(); ++i)
fout << l[i].x << ' ' << l[i].y << '\n';
return 0;
}