Pagini recente » Cod sursa (job #1667892) | Cod sursa (job #1140985) | Cod sursa (job #1965931) | Cod sursa (job #2716183) | Cod sursa (job #560529)
Cod sursa(job #560529)
#include <fstream>
#include <math.h>
#include <algorithm> //pentru sort
#define nmax 120001
#define inf 1000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
unsigned long n;
struct punct
{
long double x,y; //coordonatele
long double panta; //panta fata de cel mai din stanga punct
};
punct a[nmax]; //vectorul in care retin toate punctele
punct st[nmax]; //stiva care va contine infasuratoarea convexa
unsigned long pct=1; //indicele in vectorul a a celui mai din stanga punct
unsigned long nr; //varful stivei
struct cmp //o structura de date care contine nu date ci o functie
{
bool operator () (const punct &A,const punct &B) //bool tipul pe care il intoarce ,
{
if(A.panta==B.panta) //daca au aceeasi panta il luam pe cel mai din exterior
if(A.x==B.x) //daca si x sunt egali (pe aceeasi dreapta cu pct)
return A.y<B.y; //returneaza daca expresia este adevarata sau nu : true sau false ; daca da atunci
else return A.x<B.x;
else return A.panta<B.panta;
}
};
void citire() //citresc punctele si retin pe cel mai din stanga si in caz de egalitate pe cel mai de jos
{
fin>>n;
unsigned int i;
for(i=1;i<=n;i++)
{
fin>>a[i].x>>a[i].y;
if(a[i].x<a[pct].x)
pct=i;
else if(a[i].x==a[pct].x && a[i].y<=a[pct].x)
pct=i;
}
}
long double panta(long double xa,long double ya,long double xb,long double yb)
{
if(xa==xb)
return inf; //sa nu fie 0 la numitor
return (yb-ya)/(xb-xa);
}
void calc_pante()
{
unsigned int i;
for(i=1;i<=n;i++)
{
a[i].panta=-inf; //daca este punctul cel mai din stanga => panta cea mai mica pt a fi primul la sortare
if(i!=pct) //daca nu este punctul cel mai din stanga
a[i].panta=panta(a[pct].x,a[pct].y,a[i].x,a[i].y); //calculez panta fata de pct;
}
sort(a+1,a+n+1,cmp()); //a+1 elementul a[1] ; a+n+1 elementul a[n] ;cmp() criteriul de comparatie
//cmp is an optional function object that is used in place of < to perform comparisons between pairs of elements.
}
long double semn(long double x1,long double y1,long double x2,long double y2,long double x3,long double y3)
{
return x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
}
void infasuratoare()
{
unsigned long int i;
nr=2; //varful stivei este 2
st[1]=a[1]; //pun in stiva primele 2 numere : pct si cel cu panta cea mai mica
st[2]=a[2];
for(i=3;i<=n;++i)
{
//atata timp cat in stiva sunt mai mult de 2 elemente
//si unghiul dinte dreptele : st[nr-1]->st[nr] si st[nr]->a[i] <=180 de grade
while(nr>=2 && semn(st[nr-1].x,st[nr-1].y,st[nr].x,st[nr].y,a[i].x,a[i].y)<0)
--nr;
st[++nr]=a[i];
}
}
void afisare()
{
unsigned long i;
fout<<nr<<'\n';
for(i=1;i<=nr;i++)
fout<<st[i].x<<" "<<st[i].y<<'\n';
}
int main()
{
citire();
calc_pante();
infasuratoare();
afisare();
fin.close();
fout.close();
return 0;
}