Pagini recente » Cod sursa (job #2982332) | Cod sursa (job #2460229) | Borderou de evaluare (job #936698) | Cod sursa (job #1916388) | Cod sursa (job #1912284)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
#define pdd pair < double , double >
using namespace std;
const int NMax = 120005;
int N;
pdd v[NMax];
vector < pdd > ST;
void Read()
{
scanf("%d", &N);
for(int i=1; i<=N; ++i)
scanf("%lf %lf", &v[i].x, &v[i].y);
}
int Det(pdd a, pdd b, pdd c)
{
return (a.x*b.y + a.y*c.x + b.x*c.y - b.y*c.x - c.y*a.x - a.y*b.x );
}
void Minim()
{
for(int i=2; i<=N; ++i)
if(v[i] < v[1])
swap(v[i], v[1]);
}
struct Comparator
{
bool operator()(pdd a, pdd b)
{
return Det(v[1],a,b) > 0;
}
} cmp;
void Sortare()
{
sort(v+2, v+N+1, cmp);
}
void Algorithm()
{
for(int i=1; i<=N; ++i)
{
while(ST.size() >=2 && Det(ST[ST.size()-2], ST[ST.size()-1], v[i]) < 0)
ST.pop_back();
ST.push_back(v[i]);
}
}
void Print()
{
printf("%d\n", ST.size());
for(vector< pdd >::iterator it = ST.begin(); it != ST.end(); ++it)
printf("%.6lf %.6lf\n", it->x, it->y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
Read();
Minim();
Sortare();
Algorithm();
Print();
return 0;
}