Pagini recente » Cod sursa (job #715880) | Cod sursa (job #1397201) | Cod sursa (job #211189) | Cod sursa (job #2183142) | Cod sursa (job #1109315)
#include <fstream>
#include <cmath>
#define NMax 101
using namespace std;
fstream fin("infasuratoare.in",ios::in);
fstream fout("infasuratoare.out",ios::out);
struct Punct{float x,y;};
Punct Pcts[NMax],stiva[NMax],Min;
int n,varf;
void Citire()
{
fin>>n;
for(int i=0;i<n;i++)
fin>>Pcts[i].x>>Pcts[i].y;
}
int StangaJos()
{
int pct=0;
for(int i=1;i<n;i++)
{
if(Pcts[i].y<Pcts[pct].y)
pct=i;
else if(Pcts[i].y==Pcts[pct].y&&Pcts[i].x<Pcts[pct].x)
pct=i;
}
return pct;
}
int Cadran(int x, int y)
{
if(x>=0&&y>=0) return 0;
if(x<0) return 1;
if(x>=0&&y<0) return 2;
}
void QuickSort(int st,int dr)
{
int i,j;
double xtan;
Punct X;
if(st<dr)
{
X=Pcts[st];i=st;j=dr;
xtan=atan((X.y-Pcts[0].y)/(X.x-Pcts[0].x))+M_PI*Cadran(X.x-Pcts[0].x,X.y-Pcts[0].y);
while(i<j)
{
while( i<j && (atan( (Pcts[j].y-Pcts[0].y) / (Pcts[j].x-Pcts[0].x) )+M_PI*Cadran(Pcts[j].x-Pcts[0].x,Pcts[j].y-Pcts[0].y) )>=xtan ) j--;
Pcts[i]=Pcts[j];
while( i<j && (atan( (Pcts[i].y-Pcts[0].y) / (Pcts[i].x-Pcts[0].x) )+M_PI*Cadran(Pcts[i].x-Pcts[0].x,Pcts[i].y-Pcts[0].y) )<=xtan) i++;
Pcts[j]=Pcts[i];
}
Pcts[i]=X;
QuickSort(st,i-1);
QuickSort(i+1,dr);
}
}
void PUSH(Punct P)
{
stiva[++varf]=P;
}
void POP()
{
varf--;
}
int Produs(Punct P1,Punct P2,Punct P3)
{
return (P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y);
}
void ScanareaGraham()
{
int pct,i,prod;
pct=StangaJos();
swap(Pcts[0],Pcts[pct]);
QuickSort(1,n-1);
varf=-1;
PUSH(Pcts[0]); PUSH(Pcts[1]);
for(i=2;i<n;i++)
{
prod=Produs(stiva[varf-1],stiva[varf],Pcts[i]);
if(prod==0)//coliniare
//elimin stiva[varf] si pun in loc P[i]
{
POP();
PUSH(Pcts[i]);
}
else if(prod>0) PUSH(Pcts[i]);//la stanga
else//prod<0
{
POP();
while(Produs(stiva[varf-1],stiva[varf],Pcts[i])<0&&varf>0) POP();
PUSH(Pcts[i]);
}
}
}
void Tipar()
{
//for(int i=0;i<n;i++)
// fout<<"P["<<i<<"]("<<Pcts[i].x<<","<<Pcts[i].y<<"): "<<atan( (Pcts[i].y-Pcts[0].y)/(Pcts[i].x-Pcts[0].x) )<<endl;
fout<<varf+1;
for(int i=0;i<=varf;i++)
fout<<stiva[i].x<<" "<<stiva[i].y<<endl;
}
int main()
{
Citire();
ScanareaGraham();
Tipar();
return 0;
}