Pagini recente » Cod sursa (job #261895) | Cod sursa (job #954137) | Rating Andrei Vasile (micutu) | Cod sursa (job #779881) | Cod sursa (job #343761)
Cod sursa(job #343761)
/*
Infasuratoarea convexa - Scanarea Graham
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define N 120001
int n, ns;
struct nod {
double x, y;
nod() {}
nod(double x1, double y1) {
x=x1;
y=y1;
}
};
nod st[N], P(0x3f3f3f3f, 0x3f3f3f3f), a[N];
int isLeft(nod p0, nod p1, nod p2) {
// determin poz lui p0 fata de dreapta p1p2
// <0 este in partea stanga
// =0 pe dreapta
// >0 in partea dreapta
double d = (p0.x-p1.x)*(p2.y-p1.y)-(p0.y-p1.y)*(p2.x-p1.x);
if (d<0) return -1;
if (d>0) return 1;
return 0;
}
struct cmp {
bool operator()(const nod &a, const nod &b) const {
int t=isLeft(P,a,b);
if (t==1) return 0; // dc e pe partea dreapta => a<b
return 1;
}
};
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cin>>n;
for (int i=1; i<=n; i++)
cin>>a[i].x>>a[i].y;
//caut cel mai de jos punct si cel mai din stanga
int poz=0;
for (int i=1; i<=n; i++)
if (a[i].y<P.y) P=a[i], poz=i;
else
if (a[i].y==P.y && a[i].x<P.x) P=a[i], poz=i;
// pun cel mai de jos si cel mai din stanga element pe prima poz
nod t=a[1];
a[1]=P;
a[poz]=t;
// ordonez vectorul crescator dupa unghiul polar
sort(a+2, a+n+1,cmp());
st[++ns]=a[1];
st[++ns]=a[2];
st[++ns]=a[3];
for (int i=4; i<=n; i++) {
while (isLeft(st[ns-1], st[ns], a[i])==1) --ns;
st[++ns]=a[i];
}
cout<<ns<<endl;
for (int i=1; i<=ns; i++)
cout<<st[i].x<<" "<<st[i].y<<endl;
return 0;
}