Pagini recente » Cod sursa (job #927962) | Cod sursa (job #442178) | Cod sursa (job #2641416) | Cod sursa (job #459160) | Cod sursa (job #915264)
Cod sursa(job #915264)
#include <cstdio>
#include <algorithm>
#define nMax 120100
#define oo 1 << 30
using namespace std;
struct punct{
double x;
double y;
double panta;
};
punct a[nMax];
int p[nMax];
int n;
int minim = oo;
int pmin;
int m;
double panta(punct a, punct b){
if(a.x - b.x == 0){
return oo;
}
return (a.y - b.y)/(a.x - b.y);
}
struct cmp{
bool operator () (punct const &a, punct const &b)const{
return a.panta > b.panta;
}
};
/**
a.x | a.y | 1
b.x | b.y | 1
c.x | c.y | 1
*/
double determinant(punct a, punct b, punct 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 citire(){
scanf("%d", &n);
for(int i = 0; i < n; ++ i){
scanf("%lf %lf", &a[i].x, &a[i].y);
if(a[i].x <= minim){
if(a[i].x == minim){
if(a[i].y < a[pmin].y){
pmin = i;
}
}else{
pmin = i;
minim = a[i].x;
}
}
}
for(int i = 0; i < n; ++ i){
a[i].panta = panta(a[pmin], a[i]);
}
a[pmin].panta ++;
sort(a, a + n, cmp());
}
void infasuratoare(){
m = 2;
p[0] = 0;
p[1] = 1;
for(int i = 2; i < n; ++ i){
while(m > 2 && determinant(a[p[m - 2]], a[p[m - 1]], a[i]) > 0){
m --;
}
p[m ++] = i;
}
}
void afisare(){
printf("%d\n", m);
for(int i = 0; i < m; ++ i){
printf("%lf %lf\n", a[p[i]].x, a[p[i]].y);
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
infasuratoare();
afisare();
return 0;
}