Pagini recente » Cod sursa (job #1898729) | Cod sursa (job #324817) | Cod sursa (job #2969924) | Cod sursa (job #1629418) | Cod sursa (job #1343995)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{double x,y;} p[120001];
int nrp,v[120001],ok,pas,poz;
bool used[120001];
double pozitie(point A,point B,point C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-A.x*C.y-B.x*A.y;
}
bool test(point A,point B)
{
if(A.x!=B.x)
return A.x<B.x;
else
return A.y<B.y;
}
void afis(int poz)
{
fout<<poz<<'\n';
for(int i=poz;i>=1;i--)
{
fout.precision(6);
fout<<fixed<<p[v[i]].x<<' '<<fixed<<p[v[i]].y<<'\n';
}
}
int main()
{
fin>>nrp;
for(int i=1;i<=nrp;i++)
fin>>p[i].x>>p[i].y;
sort(p+1,p+nrp+1,test);
v[1]=1; v[2]=2; used[2]=true; poz=2; pas=1;
while(v[poz]!=1)
{
int k=v[poz]+pas;
while(pozitie(p[v[poz-1]],p[v[poz]],p[k])>0)
poz--;
v[++poz]=k;
if(v[poz]==nrp) pas=-1;
}
afis(poz-1);
return 0;
}