Pagini recente » Cod sursa (job #3258598) | Cod sursa (job #1350291) | Cod sursa (job #3245466) | Cod sursa (job #949769) | Cod sursa (job #2640421)
#include <fstream>
#include <vector>
#include <algorithm>
#include <tgmath.h>
#include <iomanip>
#include <iostream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
long double x, y;
long double unghi_polar;
};
int n;
vector < Punct > v;
int vf;
Punct s[120001];
void PUSH(Punct P)
{
++vf;
s[vf] = P;
}
void POP()
{
vf--;
}
bool sortare(Punct A, Punct B)
{
if(A.unghi_polar > B.unghi_polar) return false;
if(A.unghi_polar == B.unghi_polar)
{
if(A.y > B.y) return false;
}
return true;
}
long double ceas_trig(Punct A, Punct B, Punct C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int main()
{
fin >> n;
Punct p;
for(int i = 1; i <= n; i++)
{
fin >> p.x >> p.y;
v.push_back(p);
// cout << v[i - 1].x << " " << v[i - 1].y << "\n";
}
Punct punct_minim;
punct_minim = v[0];
for(int i = 1; i < n; i++)
{
if(v[i].y < punct_minim.y)
{
punct_minim = v[i];
}
else if(v[i].y == punct_minim.y)
{
if(v[i].x < punct_minim.x) punct_minim = v[i];
}
}
for(int i = 0; i < n; i++)
{
v[i].unghi_polar = atan2(v[i].y - punct_minim.y, v[i].x - punct_minim.x);
}
sort(v.begin(), v.end(), sortare);
PUSH(v[0]);
PUSH(v[1]);
for(int i = 2; i < n; i++)
{
long double o = ceas_trig(s[vf - 1], s[vf], v[i]);
if(o == 0)
{
POP();
PUSH(v[i]);
}
else
{
if(o > 0)
{
PUSH(v[i]);
}
else
{
while(o <= 0 && vf > 1)
{
POP();
o = ceas_trig(s[vf - 1], s[vf], v[i]);
}
PUSH(v[i]);
}
}
}
fout << vf << "\n";
for(int i = 1; i <= vf; i++)
{
fout << fixed << setprecision(6) << s[i].x << " " << s[i].y << "\n";
}
return 0;
}