Pagini recente » Cod sursa (job #444935) | Cod sursa (job #1115761) | Cod sursa (job #467486) | Cod sursa (job #3209662) | Cod sursa (job #1756626)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef struct point
{
double x, y;
public:
point(double x, double y) : x(x), y(y) {};
}Point;
bool cmp(Point* p1, Point* p2)
{
if(p1->x == p2->x)
return p1->y < p2->y;
else
return p1->x < p2->x;
}
double CrossProduct(Point* O, Point* A, Point* B)
{
return (A->x - O->x) * (B->y - O->y) - (A->y - O->y) * (B->x - O->x);
}
int main()
{
ifstream fin;
ofstream fout;
fout.open("infasuratoare.out");
fin.open("infasuratoare.in");
int n;
double x, y;
const double EPS = 1e-12;
fin >> n;
Point** pointsList = new Point*[n + 1]();
for(int i = 1; i <= n; i++)
{
fin >> x >> y;
pointsList[i] = new Point(x,y);
}
sort(pointsList + 1, pointsList + n + 1, cmp);
bool *viz = new bool[n + 1]();
int st[n + 1];
int head = 2;
st[1] = 1; st[2] = 2;
viz[2] = true;
for(int i = 1, p = 1; i > 0; i += ( p = (i == n ? -p : p)))
{
if(viz[i]) continue;
while(head >= 2 && CrossProduct(pointsList[st[head - 1]], pointsList[st[head]], pointsList[i]) < EPS)
{
viz[st[head--]] = false;
}
st[++head] = i;
viz[i] = true;
}
fout << head - 1 << "\n";
fout << setprecision(6) << fixed;
for(int i = 1; i < head; i++)
fout << pointsList[st[i]]->x << " " << pointsList[st[i]]->y << "\n";
fin.close();
fout.close();
return 0;
}