Pagini recente » Cod sursa (job #1413766) | Cod sursa (job #799093) | Cod sursa (job #1085318) | Cod sursa (job #583983) | Cod sursa (job #2296396)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct coor
{
double x;
double y;
} t[120002];
int i,j,n,m,poz,a,b,v[120003],c[120003];
bool comp(coor a,coor b)
{
if (a.x>b.x) return 0;
if (a.x<b.x) return 1;
if (a.y>b.y) return 0;
return 1;
}
double det(coor p1,coor p2,coor p3)
{
return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x;
}
int main()
{
fin>>n;
for (i=1;i<=n;i++)
fin>>t[i].x>>t[i].y;
sort(t+1,t+n+1,comp);
v[1]=1;
v[2]=2;
c[2]=1;
poz=2;
for (i=3;i<=n;i++)
{
if (c[i]) continue;
while (poz>=2 && det(t[v[poz-1]],t[v[poz]],t[i])<0)
c[v[poz--]]=0;
poz++;
v[poz]=i;
c[i]=1;
}
for (i=n;i>1;i--)
{
if (c[i]) continue;
while (poz>=2 && det(t[v[poz-1]],t[v[poz]],t[i])<0)
c[v[poz--]]=0;
poz++;
v[poz]=i;
c[i]=1;
}
fout<<poz<<"\n"<<fixed<<setprecision(6);
for(i=1;i<=poz;i++)
fout<<t[v[i]].x<<" "<<t[v[i]].y<<"\n";
return 0;
}