Pagini recente » Cod sursa (job #2698702) | Cod sursa (job #228164) | Cod sursa (job #799510) | Cod sursa (job #619586) | Cod sursa (job #800887)
Cod sursa(job #800887)
#include <cstdio>
#include <algorithm>
#include <stack>
#define abs(x) ((x < 0) ? -x : x)
#define nMax 120005
#define inf 1009999999
#define max(a, b) ((a > b) ? a : b)
using namespace std;
struct punct{
double x;
double y;
double panta;
};
int n;
punct p[nMax];
double d[nMax];
stack <punct> s;
struct cmp{
bool operator () (const punct &a, const punct &b)const{
return a.panta > b.panta;
}
};
double panta (punct p1, punct p2){
if (p1.x - p2.x == 0){
return inf;
}
return (double)(p1.y - p2.y)/(double)(p1.x - p2.x);
}
double determinant (punct p1, punct p2, punct p3){
return p1.x * p2.y + p2.x * p3.y + p1.y * p3.x
- p3.x * p2.y - p1.y * p2.x - p1.x * p3.y;
}
void citire(){
punct pMin;
pMin.x = inf;
pMin.y = inf;
scanf ("%d", &n);
int pct;
for (int i = 0; i < n; ++ i){
scanf ("%lf %lf", &p[i].x, &p[i].y);
if (p[i].x < pMin.x){
pMin = p[i];
pct = i;
}else if (p[i].x == pMin.x){
if (p[i].y < pMin.y){
pMin = p[i];
pct = i;
}
}
}
for (int i = 0; i < n; ++ i){
p[i].panta = panta (pMin, p[i]);
}
p[pct].panta = inf + 1;
sort (p, p + n, cmp());
}
void infasoara(){
s.push (p[0]);
s.push (p[1]);
int nr = 2;
for (int i = 2; i < n; ++ i){
punct p2 = s.top();
s.pop();
nr --;
punct p1 = s.top();
while (determinant(p1, p2, p[i]) > 0){
p2 = p1;
s.pop();
p1 = s.top();
nr --;
}
s.push (p2);
s.push (p[i]);
nr += 2;
}
printf ("%d\n", nr);
while (!s.empty()){
printf ("%lf %lf\n", s.top().x, s.top().y);
s.pop();
}
}
int main(){
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
citire();
infasoara();
return 0;
}