Pagini recente » Cod sursa (job #3246375) | Cod sursa (job #1286418) | Cod sursa (job #1018927) | Cod sursa (job #571329) | Cod sursa (job #1369162)
#include <iostream>
#include <fstream>
#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 cmp(punct a, punct b)
{
if(a.x == b.x) return a.y < b.y;
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()
{
ifstream fin("infasuratoare.in");
fin >> n;
for(int i = 0; i < n; i++)
fin >> pct[i].x >> pct[i].y;
}
void solve()
{
sort(pct, pct+n, cmp);
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]);
}
for(int i = n-2; i >= 0; 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;
}