Pagini recente » Diferente pentru info-oltenia-2019/individual/solutii intre reviziile 1 si 2 | Rezultatele filtrării | Statistici Groza Vlad (vlad_groza013) | Treap-uri | Cod sursa (job #1553856)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#define NMAX 1200050
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x;
double y;
point()
{
this->x = 0;
this->y = 0;
}
point(double x, double y)
{
this->x = x;
this->y = y;
}
point(const point &P)
{
this->x = P.x;
this->y = P.y;
}
bool operator<(point &P)
{
if (this->x < P.x)
return true;
if (P.x < this->x)
return false;
if (this->y < P.y)
return true;
return false;
}
friend istream &operator>>(istream &stream, point& P);
friend ostream &operator<<(ostream &stream, point& P);
};
istream &operator>>(istream &stream, point &P)
{
stream >> P.x >> P.y;
return stream;
}
ostream &operator<<(ostream &stream, point &P)
{
stream << P.x << " " << P.y << "\n";
return stream;
}
point V[NMAX];
int N;
point vect(const point &P1, const point &P2)
{
return point(P2.x - P1.x, P2.y - P1.y);
}
double cross_product(const point &P1, const point &P2, const point &P3)
{
point A, B;
A=vect(P1, P2);
B=vect(P1, P3);
return (A.x*B.y - A.y*B.x);
}
bool cmp(const point &P1, const point &P2)
{
return cross_product(V[1], P1, P2) < 0;
}
void _sort()
{
int poz = 1;
for (int i = 2; i <= N; i++)
{
if (V[i] < V[poz])
{
poz = i;
}
}
swap(V[1], V[poz]);
sort(V + 2, V + N + 1, cmp);
}
vector<point> convex_hull()
{
vector<point> st;
_sort();
st.push_back(V[1]);
st.push_back(V[2]);
for (int i = 3; i <= N; i++)
{
while (st.size() > 1 && cross_product(st[st.size() - 2], st[st.size() - 1], V[i]) > 0)
{
st.pop_back();
}
st.push_back(V[i]);
}
return st;
}
int main()
{
point P;
fin >> N;
for (int i = 1; i <= N; i++)
{
fin >> P;
V[i] = P;
}
vector<point> sol;
sol = convex_hull();
fout << sol.size() << '\n';
fout << fixed;
fout << setprecision(6);
for (int i = sol.size() - 1; i >= 0; i--)
{
fout << sol[i];
}
return 0;
}