Pagini recente » Cod sursa (job #235791) | Cod sursa (job #1750261) | Cod sursa (job #221292) | Cod sursa (job #1558046) | Cod sursa (job #1363721)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
struct punct
{
double x, y;
punct(double x = 0, double y = 0):x(x), y(y){}
};
bool cmp1(punct a, punct b)
{
if(a.y < b.y) return true;
if(a.y > b.y) return false;
return a.x > b.x;
}
bool cmp2(punct a, punct b)
{
if(a.y > b.y) return true;
if(a.y < b.y) return false;
return a.x < b.x;
}
bool operator == (punct a, punct b)
{
return a.x == b.x && a.y == b.y;
}
inline double det(punct a, punct b, punct c)
{
return a.x*b.y + b.x*c.y + a.y*c.x - b.y*c.x - a.y*b.x - a.x*c.y;
}
vector<punct> v;
punct pct[120010];
int n;
void citire()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%lf%lf", &pct[i].x, &pct[i].y);
}
void solve()
{
sort(pct, pct+n, cmp1);
for(int i = 0; i < n; i++)
{
while(v.size() >= 2 && det(v[v.size()-2], v[v.size()-1], pct[i]) < 0
|| v.size() >= 1 && v[v.size()-1] == pct[i])
v.pop_back();
v.push_back(pct[i]);
}
sort(pct, pct+n, cmp2);
for(int i = 0; i < n; i++)
{
while(v.size() >= 2 && det(v[v.size()-2], v[v.size()-1], pct[i]) < 0
|| v[v.size()-1] == pct[i])
v.pop_back();
v.push_back(pct[i]);
}
if(v.back() == v.front())
v.pop_back();
}
void afisare()
{
printf("%d\n", v.size());
for(int i = 0; i < v.size(); i++)
printf("%lf %lf\n", v[i].x, v[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
solve();
afisare();
return 0;
}