Pagini recente » Cod sursa (job #2794541) | Cod sursa (job #2853677) | Cod sursa (job #32706) | Cod sursa (job #1043490) | Cod sursa (job #2342911)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const double EPS=1e-12;
struct point{
double x, y;
}v[Nmax];
int n;
int st[Nmax], top;
double x, y;
bool seen[Nmax];
bool cmp(point a, point b)
{
if(a.x == b.x) return a.y < b.y;
return a.x<b.x;
}
double det(int a, int b, int c)
{
double d=0;
d+=v[a].x*v[b].y;
d+=v[a].y*v[c].x;
d+=v[b].x*v[c].y;
d-=v[c].x*v[b].y;
d-=v[c].y*v[a].x;
d-=v[b].x*v[a].y;
return d;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> x >> y;
v[i]={x, y};
}
sort(v+1, v+n+1, cmp);
st[1]=1, st[2]=2;
seen[2]=1;
top=2;
for (int i = 3; i <= n; i++)
{
if(seen[i] == 1) continue;
while(top>1 && det(st[top], st[top-1], i)<EPS)
{
seen[st[top]]=0;
top--;
}
top++;
st[top]=i;
seen[i]=1;
}
for (int i = n-1; i >= 1; i--)
{
if(seen[i] == 1) continue;
while(top>1 && det(st[top], st[top-1], i)<EPS)
{
seen[st[top]]=0;
top--;
}
top++;
st[top]=i;
seen[i]=1;
}
top--;
g << top << '\n';
for (int i = top; i >= 1; i--)
g << fixed << setprecision(6) << v[st[i]].x << " " << fixed << setprecision(6) << v[st[i]].y << '\n';
return 0;
}