Pagini recente » Cod sursa (job #2044074) | Cod sursa (job #543135) | Cod sursa (job #579900) | Cod sursa (job #1565007) | Cod sursa (job #1369037)
#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-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.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.00000001)
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.00000001
|| 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;
}