Pagini recente » Cod sursa (job #2035351) | Cod sursa (job #1840018) | Cod sursa (job #589867) | Cod sursa (job #2429846) | Cod sursa (job #1607942)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct punct
{
double x, y;
punct(double x = 0, double y = 0) : x(x), y(y) { }
bool operator()(punct a, punct b)
{
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
};
int n;
vector<punct> poly;
vector<punct> s1, s2;
void citire()
{
double x, y;
scanf("%d\n", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf %lf\n", &x, &y);
poly.push_back(punct(x, y));
}
}
double determinant(punct a, punct b, punct c)
{
return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - b.x*a.y - a.x*c.y;
}
void add(vector<punct> &s, punct p)
{
while (s.size() >= 2 && determinant(s[s.size()-2], s[s.size()-1], p) < 0)
s.pop_back();
s.push_back(p);
}
void solve()
{
sort(poly.begin(), poly.end(), punct());
s1.push_back(poly[0]);
for (int i = 1, t = poly.size(); i < t; i++)
add(s1, poly[i]);
s2.push_back(poly.back());
for (int i = poly.size()-2; i >= 0; --i)
add(s2, poly[i]);
s1.pop_back();
s2.pop_back();
for (int i = 0, t = s2.size(); i < t; i++)
s1.push_back(s2[i]);
printf("%d\n", s1.size());
for (int i = 0, t = s1.size(); i < t; i++)
printf("%lf %lf\n", s1[i].x, s1[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
solve();
return 0;
}