Pagini recente » Cod sursa (job #396812) | Cod sursa (job #549746) | Cod sursa (job #1955027) | Cod sursa (job #2164465) | Cod sursa (job #1547467)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int nmax = 120005;
struct point {double x, y;} v[nmax];
inline double sarrus(point a, point b, point c)
{
return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - c.y*a.x - b.x*a.y;
}
inline bool cmp(point a, point b)
{
return sarrus(v[1], a, b) > 0;
}
int main()
{
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
ios_base::sync_with_stdio(false);
int n, i, st[nmax], top=0, poz=1;
fin >> n;
for(i=1; i<=n; i++)
{
fin >> v[i].x >> v[i].y;
if(v[i].x < v[poz].x) poz=i;
if(v[i].x == v[poz].x && v[i].y < v[poz].y) poz=i;
}
swap(v[1], v[poz]);
sort(v+2, v+n+1, cmp);
v[n+1]=v[1];
st[++top]=1;
for(i=2; i<=n; i++)
{
st[++top]=i;
while(sarrus(v[st[top-1]], v[st[top]], v[i+1]) < 0) top--;
}
fout << setprecision(6) << fixed << top << "\n";
for(i=1; i<=top; i++)
fout << v[st[i]].x << " " << v[st[i]].y << "\n";
fin.close();
fout.close();
return 0;
}