Pagini recente » Cod sursa (job #2667709) | Cod sursa (job #1904223) | Cod sursa (job #46909) | Cod sursa (job #1486266) | Cod sursa (job #2089660)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int N = 120002;
const double mic = 1e-12;
int st[N];
bool inStack[N];
struct punct{
double x,y;
}v[N];
bool cmp(punct a, punct b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
double prod(punct o, punct a, punct b){
return ((a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y));
}
void graham(int n){
int poz = 2, sens = 1;
sort(v+1, v+n+1, cmp);
st[1] = 1;
st[2] = 2;
inStack[2] = true;
for(int i=1;i>0;i+=sens){
if(i == n)
sens *= -1;
if(inStack[i] == false){
while(poz >= 2 && (prod(v[st[poz - 1]], v[st[poz]], v[i]) < mic))
inStack[st[poz--]] = false;
st[++poz] = i;
inStack[i] = true;
}
}
out<<poz - 1<<"\n";
out<<setprecision(6)<<fixed;
for(int i=1;i<poz;i++)
out<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
int main()
{
int n;
in>>n;
for(int i=1;i<=n;i++)
in>>v[i].x>>v[i].y;
in.close();
graham(n);
out.close();
return 0;
}