Pagini recente » Cod sursa (job #2192674) | Cod sursa (job #48833) | Cod sursa (job #1981341) | Cod sursa (job #3164238) | Cod sursa (job #236648)
Cod sursa(job #236648)
#include<stdio.h>
#include<algorithm>
#include<vector>
#define mkp make_pair
#define pb push_back
using namespace std;
const int maxn = 1200000;
vector<pair<double,double> > VECT;
double ARIE;
int N,ST[maxn],VER[maxn];
//Semnul verifica ca triunghiul dat este parcurs in ordine invers trigonometrica
double semn(int i1,int i2,int i3)
{
return VECT[i1].first * VECT[i2].second + VECT[i2].first * VECT[i3].second + VECT[i3].first * VECT[i1].second - VECT[i1].second * VECT[i2].first - VECT[i2].second * VECT[i3].first - VECT[i3].second * VECT[i1].first;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&N);
for(int i = 1; i <= N; ++i)
{
double x = 0,y = 0;
scanf("%lf %lf\n",&x,&y);
VECT.pb(mkp(x,y));
}
//Verific sa fie sortat
reverse(VECT.begin(),VECT.end());
if (next_permutation(VECT.begin(),VECT.end())) sort(VECT.begin(),VECT.end());
ST[ST[0] = 1] = 1;
// Prima data cand fac stiva pentru partea din dreapta dreptei (Pjos,Psus)
for(int i = 2;i <= N; ++i)
{
if (VER[i]) continue;
while(ST[0] >= 2 && semn(ST[ST[0] - 1] - 1,ST[ST[0]] - 1,i - 1) > 0)
{
VER[ST[ST[0]]] = 0;
ST[0]--;
}
ST[++ST[0]] = i;
VER[i] = 1;
}
// A 2-a oara cand fac stiva pentru partea din stanga dreptei (Pjos,Psus)
for(int i = N;i; --i)
{
if (VER[i]) continue;
while(ST[0] >= 2 && semn(ST[ST[0] - 1] - 1,ST[ST[0]] - 1,i - 1) > 0){VER[ST[ST[0]]] = 0;ST[0]--;}
ST[++ST[0]] = i;
VER[i] = 1;
}
printf("%d\n",ST[0] - 1);
for(int i = 1;i < ST[0]; ++i)
{
printf("%lf %lf\n",VECT[ST[i] - 1].first,VECT[ST[i] - 1].second);
}
return 0;
}