Pagini recente » Statistici Ella Rose (ElizaT) | Profil oganea | Monitorul de evaluare | Cod sursa (job #569743) | Cod sursa (job #1414744)
#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(A, B, Punct[1]) < 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].Y < Punct[ind].Y)
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].X, Sol[i].Y);
}
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;
}