Pagini recente » Cod sursa (job #3205958) | Cod sursa (job #3175518) | Cod sursa (job #2981337) | Cod sursa (job #2246993) | Cod sursa (job #1553836)
#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)
{
return(this->x < P.x || (!(this->x < P.x) && this->y < P.y));
}
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)? 1 : 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();
_sort();
fout << sol.size() << '\n';
fout << fixed;
fout << setprecision(6);
for (int i = sol.size() - 1; i >= 0; i--)
{
fout << sol[i];
}
return 0;
}