Pagini recente » Cod sursa (job #1609458) | Cod sursa (job #2127897) | Cod sursa (job #2976513) | Cod sursa (job #1053565) | Cod sursa (job #2774759)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct
{
double x, y;
};
Punct punctinit;
Punct nextToTop(stack<Punct>& S)
{
Punct p = S.top();
S.pop();
Punct res = S.top();
S.push(p);
return res;
}
int orientare(Punct pst, Punct pint, Punct pfin)
{
int ok = (pint.y - pst.y) * (pfin.x - pint.x) - (pint.x - pst.x) * (pfin.y - pint.y);
if (ok == 0)
return 0;
if (ok > 0)
return 1;
else
return 2;
}
double distanta(Punct p1, Punct p2)
{
return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.x) * (p2.y - p1.x);
}
int criteriu(const void* nr1, const void* nr2)
{
Punct* p1 = (Punct*)nr1;
Punct* p2 = (Punct*)nr2;
int ok = orientare(punctinit, *p1, *p2);
if (ok == 0)
if (distanta(punctinit, *p2) >= distanta(punctinit, *p1))
return -1;
else
return 1;
if (ok== 2)
return -1;
else
return 1;
}
void puncte_poligon(vector<Punct> puncte, int n)
{
double ymin, minpos=0;
ymin = puncte[0].y;
for(int i=1;i<n;i++)
if ((puncte[i].y < ymin) || (puncte[i].y == ymin && puncte[i].x < puncte[minpos].x))
{
ymin = puncte[i].y;
minpos = i;
}
Punct aux;
aux = puncte[0];
puncte[0] = puncte[minpos];
puncte[minpos] = aux;
punctinit = puncte[0];
qsort(&puncte[1], n - 1, sizeof(Punct), criteriu);
int nr = 1;
for (int i = 1; i < n; i++)
{
while (i < n - 1 && orientare(punctinit, puncte[i], puncte[i + 1]) == 0)
i++;
puncte[nr] = puncte[i];
nr++;
}
if (nr < 3)
return;
stack<Punct> Spuncte;
Spuncte.push(puncte[0]);
Spuncte.push(puncte[1]);
Spuncte.push(puncte[2]);
for (int i = 3; i < nr; i++)
{
while (Spuncte.size() > 1 && orientare(nextToTop(Spuncte), Spuncte.top(), puncte[i]) != 2)
Spuncte.pop();
Spuncte.push(puncte[i]);
}
g << Spuncte.size() << "\n";
while (!Spuncte.empty())
{
Punct p = Spuncte.top();
g<<setprecision(6)<<fixed<< "(" << p.x << ", " << p.y << ")" <<"\n";
Spuncte.pop();
}
}
int main()
{
int n;
vector<Punct> puncte;
f >> n;
for (int i = 0; i < n; i++)
{
Punct punct;
f >> punct.x >> punct.y;
puncte.push_back(punct);
}
puncte_poligon(puncte, n);
return 0;
}