Pagini recente » Cod sursa (job #373206) | Cod sursa (job #3239705) | Cod sursa (job #2025038) | Cod sursa (job #2510006) | Cod sursa (job #1369042)
#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++)
cin >> 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) //-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
|| 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;
}