Pagini recente » Cod sursa (job #499965) | Cod sursa (job #3201443) | Cod sursa (job #2723836) | Cod sursa (job #2918953) | Cod sursa (job #1413810)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
const double EPS=1e-12;
#define MAX 120010
#define cout fout
typedef double d;
d cross_product(pair<d, d> O, pair<d, d> A, pair<d, d> B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
pair<d, d> a[MAX];
int dr, viz[MAX], st[MAX];
int main()
{
int n, i;
fin >> n;
for(i = 1 ; i <= n ; i++)
{
fin >> a[i].x >> a[i].y;
}
sort(a + 1, a + n + 1);
for(i = 1 ; i <= n ; i++)
{
if(viz[i])
continue;
while(dr >= 2 && cross_product(a[st[dr - 1]], a[st[dr]], a[i]) < EPS)
viz[st[dr--]] = 0;
st[++dr] = i;
viz[i] = 1;
}
for(i = n ; i >= 1 ; i--)
{
if(viz[i])
continue;
while(dr >= 2 && cross_product(a[st[dr - 1]], a[st[dr]], a[i]) < EPS)
viz[st[dr--]] = 0;
st[++dr] = i;
viz[i] = 1;
}
cout << dr << "\n";
cout << setprecision(6) << fixed;
for(i = 1 ; i <= dr ; i++)
cout << a[st[i]].x << " " << a[st[i]].y << "\n";
}