Pagini recente » Cod sursa (job #1392919) | Cod sursa (job #1605761) | Cod sursa (job #2517147) | Cod sursa (job #1606702) | Cod sursa (job #2263544)
#include <cstdio>
#include <algorithm>
using namespace std;
struct punct2D
{
double x, y;
}punctCmp;
int testOrientare(punct2D &a, const punct2D &b, const punct2D &c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(punct2D &a, punct2D &b)
{
return (testOrientare(punctCmp,a,b) > 0);
}
class Stiva
{
private :
int nrElemente;
punct2D* elemente;
public :
Stiva()
{
nrElemente = 0;
elemente = new punct2D[120001];
}
bool add(const punct2D &nr)
{
elemente[nrElemente] = nr;
nrElemente++;
return 1;
}
bool removeElement()
{
if (nrElemente == 0)
return 0;
nrElemente--;
return 1;
}
int getNumberOfElements()
{
return nrElemente;
}
bool afisareStiva(FILE* &afisare)
{
for (int i = 0 ; i < nrElemente ; i++)
fprintf(afisare,"%lf %lf\n",elemente[i].x,elemente[i].y);
return 1;
}
punct2D getPoint(const int &i)
{
return elemente[i - 1];
}
};
int main()
{
FILE* citire = fopen("infasuratoare.in","r");
FILE* afisare = fopen("infasuratoare.out","w");
int n(0);
fscanf(citire,"%d\n",&n);
punct2D* puncte = new punct2D[n + 1];
int pctCmp(1);
for (int i = 1 ; i <= n ; i++)
{
fscanf(citire,"%lf %lf",&puncte[i].x,&puncte[i].y);
/// punctCompar trebuie sa fie cel mai de jos punct, stanga in caz de egalitate
if (puncte[i].y < puncte[pctCmp].y)
pctCmp = i;
else if (puncte[i].y == puncte[pctCmp].y)
{
if (puncte[i].x < puncte[pctCmp].x)
pctCmp = i;
}
}
{
punct2D aux;
aux = puncte[pctCmp];
puncte[pctCmp] = puncte[1];
puncte[1] = aux;
punctCmp = puncte[1];
}
sort(puncte + 2, puncte + n + 1,cmp);
Stiva stiva;
stiva.add(puncte[1]);
stiva.add(puncte[2]);
for (int i = 3 ; i <= n ; i++)
{
punct2D a = stiva.getPoint(stiva.getNumberOfElements() - 1);
punct2D b = stiva.getPoint(stiva.getNumberOfElements());
while(testOrientare(a,b,puncte[i]) <= 0 && stiva.getNumberOfElements() > 1)
{
stiva.removeElement();
a = stiva.getPoint(stiva.getNumberOfElements() - 1);
b = stiva.getPoint(stiva.getNumberOfElements());
}
stiva.add(puncte[i]);
}
fprintf(afisare,"%d\n",stiva.getNumberOfElements());
stiva.afisareStiva(afisare);
return 0;
}