Pagini recente » Cod sursa (job #2286439) | Cod sursa (job #2675561) | Cod sursa (job #1641033) | Cod sursa (job #895096) | Cod sursa (job #1538926)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct{float x,y;};
punct p,q,r,v[100] ;
int n,i,j,jj,viz[100],st[100];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bool ff(punct p1, punct p2)//ordonate dupa x si la x egal dupa y
{
if (p1.x != p2.x) return p1.x < p2.x ;
else return p1.y < p2.y ;
}
int viraj(punct p, punct q, punct r)
{
//Returns -1, 0, 1 daca p,q,r la dreapta , pe linie , la stanga
return (q.x - p.x)*(r.y - p.y) - (r.x - p.x)*(q.y - p.y);
}
int main()
{
// citesc n puncte in plan
f>>n; for(i=1;i<=n;i++) f>>v[i].x>>v[i].y;
//sortez dupa x si la x egal dupa y
sort(v+1,v+n+1,ff);
//for(i=1;i<=n;i++) g<<v[i].x<<" "<<v[i].y<<endl;// afisare sortare
st[1]=1;
st[2]=2;
viz[1]=viz[2]=1;
j=2;
for(i=3;i<=n;i++)
{ //g<<v[i].x<<"kk "<<v[i].y<<endl;
while(viraj(v[st[j-1]],v[st[j]],v[i])<1&&j>1){//g<<viraj(v[st[j-1]],v[st[j]],v[i])<<endl;
viz[st[j]]=0;j--;}//cat timp punctul i se afla in dreapta sau coliniar
j++;st[j]=i; viz[i]=1;
}// punctul se afla in stanga si fac viraj stanga
// g<<j<<" "<<v[st[j]].x<<" "<<v[st[j]].y<<endl;}
// for(i=1;i<=j;i++) g<<v[st[i]].x<<" "<<v[st[i]].y<<endl;// afisare 1/2 infasuratoare
// for(i=1;i<=n;i++) g<<viz[i]<<" ";
// g<<endl;
//g<<"====l"<<endl;
for(i=n;i>=1;i--)
if(viz[i]==0)
{//g<<v[i].x<<"kk "<<v[i].y<<endl;
while(viraj(v[st[j-1]],v[st[j]],v[i])<1&&j>1){//g<<viraj(v[st[j-1]],v[st[j]],v[i])<<endl;
viz[st[j]]=0;j--;}//cat timp punctul i se afla in dreapta sau coliniar
j++;st[j]=i; viz[i]=1;
// g<<v[st[j]].x<<" "<<v[st[j]].y<<endl;//
// punctul se afla in stanga si fac viraj stanga
} g.precision(6);
for(i=1;i<=j;i++) g<<v[st[i]].x<<" "<<v[st[i]].y<<endl;// afisare 1/2 infasuratoare
// for(i=1;i<=n;i++) g<<viz[i]<<" ";
f.close();
g.close();
return 0;
}