Pagini recente » Istoria paginii planificare/camp-chuckie | Istoria paginii planificare/sedinta-20110801 | Istoria paginii preoji2016/11-12 | Rating Ianc Andrei (andy95) | Cod sursa (job #1414745)
#include<bits/stdc++.h>
#define Nmax 120005
#define Point pair < double , double >
#define X first
#define Y second
using namespace std;
int N, Sol_DIM;
Point Punct[Nmax], Sol[Nmax];
double _produs(Point A, Point B, Point C)
{
return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}
bool _cmp(Point A, Point B)
{
return _produs(Punct[1], A, B) < 0;
}
void _Read()
{
int ind = 1;
freopen("infasuratoare.in","r", stdin);
scanf("%d", &N);
for(int i = 1; i <= N; ++ i) {
scanf("%lf %lf", &Punct[i].X, &Punct[i].Y);
if(Punct[i] < Punct[ind])
ind = i;
}
swap(Punct[ind], Punct[1]);
sort(Punct + 2, Punct + 1 + N, _cmp);
}
void _Write()
{
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", Sol_DIM);
for(int i = 1; i <= Sol_DIM; ++ i)
printf("%lf %lf\n", Sol[i]);
}
void _Infasuratoare()
{
Sol[1] = Punct[1];
Sol[Sol_DIM = 2] = Punct[2];
for(int i = 3; i <= N; ++ i) {
while(Sol_DIM >= 2 && _produs(Sol[Sol_DIM - 1], Sol[Sol_DIM], Punct[i]) > 0)
Sol_DIM --;
Sol[++ Sol_DIM] = Punct[i];
}
_Write();
}
int main()
{
_Read();
_Infasuratoare();
return 0;
}