Pagini recente » Cod sursa (job #3199775) | Cod sursa (job #797197) | Cod sursa (job #1160941) | Cod sursa (job #1487718) | Cod sursa (job #1509039)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
#define MAX 120010
#define eps 1e-12
typedef double d;
pair<d, d> a[MAX];
int st[MAX], viz[MAX], dr;
d cross_product(pair<d, d> o, pair<d, d> a, pair<d, d> b)
{
a.x -= o.x;
a.y -= o.y;
b.x -= o.x;
b.y -= o.y;
return a.x * b.y - a.y * b.x;
}
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);
st[1] = 1;
st[2] = 2;
dr = 2;
viz[2] = 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;
dr--;
}
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;
dr--;
}
st[++dr] = i;
viz[i] = 1;
}
fout << dr - 1 << "\n";
for(i = 2 ; i <= dr ; i ++)
{
fout << a[st[i]].x << " " << a[st[i]].y << "\n";
}
}