Pagini recente » Cod sursa (job #1112428) | Cod sursa (job #1217656) | Cod sursa (job #2969747) | Cod sursa (job #1257936) | Cod sursa (job #1344936)
#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,k;
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=1;i<=poz;i++)
{
fout.precision(6);
fout<<fixed<<p[v[i]].x<<' '<<fixed<<p[v[i]].y<<'\n';
}
}
int poligon()
{
int k;
while(v[poz]!=1)
{
k=v[poz]+pas;
while(used[k]==true) k=k+pas;
while(pozitie(p[v[poz-1]],p[v[poz]],p[k])<=0 && poz>=2)
used[v[poz]]=false,poz--;
if(poz==1) return 0;
v[++poz]=k; used[k]=true;
if(k==nrp) pas=-pas;
}
return 1;
}
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;
for(int i=2;i<=nrp;i++)
{
poz=2; pas=1;
v[2]=i; used[i]=true;
if(poligon()==1) break;
used[i]=false;
}
afis(poz-1);
return 0;
}