Pagini recente » Cod sursa (job #13598) | Cod sursa (job #1359304) | Cod sursa (job #2707761) | Cod sursa (job #2694507) | Cod sursa (job #2176298)
#include <iostream>
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
#define x first
#define pdd pair < double, double >
#define y second
using namespace std;
const int NMax = 120005;
pair < double, double > v[NMax];
vector < pair < double, double > > st;
int N;
void Read()
{
scanf("%d",&N);
for(int i=1; i<=N; ++i)
{
scanf("%lf%lf", &v[i].x, &v[i].y);
}
}
void Select_Mini()
{
for(int i=2; i<=N; ++i)
if(v[1] < v[i])
swap(v[1],v[i]);
}
double Det(pair < double, double > a,
pair < double, double > b,
pair < double, double > c)
{
return (b.y-a.y)*(c.x-b.x)-(c.y - b.y)*(b.x-a.x);
}
bool cmp(pair < double, double > x, pair < double, double > y)
{
return Det(v[1],x,y) < 0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
Read();
Select_Mini();
sort(v+2, v+N+1, cmp);
int sz;
for(int i=1; i<=N; ++i)
{
sz = st.size();
while(st.size() >=2 && Det(st[sz-2],st[sz-1],v[i]) > 0)
{
st.pop_back();
sz = st.size();
}
st.push_back(v[i]);
}
printf("%d\n",st.size());
for(int i=0; i<st.size(); ++i)
{
printf("%lf %lf\n",st[i].first,st[i].second);
}
return 0;
}