Pagini recente » Clasament pregatireoji_clasa_xi-xii | Cod sursa (job #2751245) | Cod sursa (job #3150409) | Cod sursa (job #2897777) | Cod sursa (job #1921666)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x;
double y;
};
int n, vf;
point st[120005], p[120005], P;
int det(point p1, point p2, point p3)
{
return (p1.x * p2.y + p1.y * p3.x + p2.x * p3.y - p2.y * p3.x - p3.y * p1.x - p1.y * p2.x);
}
bool cmp(point a, point b)
{
return det(p[0], a, b) >= 0;
}
int main()
{
int poz;
f >> n;
point a, b, c;
P.x = 1000000000;
P.y = 1000000000;
for(int i = 0; i < n; i++)
{
f >> p[i].x >> p[i].y;
if(P.x > p[i].x)
{
P.x = p[i].x;
P.y = p[i].y;
poz = i;
}
else if(P.x == P.y)
{
if(P.y > p[i].y)
{
P.x = p[i].x;
P.y = p[i].y;
poz = i;
}
}
}
swap(p[poz], p[0]);
sort(p+1,p+n,cmp);
st[0] = p[0];
st[1] = p[1];
vf = 1;
p[n] = p[0];
for(int i = 2; i <= n; i++)
{
while(vf > 0 && det(st[vf - 1], st[vf], p[i]) < 0) vf--;
st[++vf] = p[i];
}
for(int i = 0; i < vf; i++)
{
g << fixed << st[i].x <<" "<< st[i].y<<"\n";
}
return 0;
}