Pagini recente » Cod sursa (job #823493) | Cod sursa (job #2120182) | Cod sursa (job #676038) | Cod sursa (job #433654) | Cod sursa (job #1335428)
//Infasuratoare Convexa- INFOARENA
//Graham Scan- Andreimdv
#include <iostream>
#include<iomanip>
#include<algorithm>
#include<fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define point pair<double,double>
#define x first
#define y second
pair<double,double> v[130000];
pair<double,double> st[130000];
double minn=1000000000;
int top,pos,n,i;
double cross(point a, point b, point c) //compararea unghiului polar folosind panta dreptelor ab si ac
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(point a, point b)
{
return cross(v[1],a,b)>0;
}
int main()
{
fin>>n;
for(i=1;i<=n;++i)
{
fin>>v[i].x>>v[i].y;
if(v[i].y<minn) //cel mai de jos pct
{
minn=v[i].y;
pos=i;
}
}
swap(v[pos],v[1]); // cel mai de jos pct se afla pe pozitia 1;
//ETAPA 1
//sort dupa polar angle:
sort(v+2,v+n+1,cmp);
//ETAPA 2
//Scanarea Graham
st[1]=v[1]; //primele 2 pct
st[2]=v[2];
top=2;
for(i=3;i<=n;++i)
{
while(cross(st[top-1],st[top],v[i])<0) //cat timp urmatorul punct reprezinta o intoarcere la dreapta, pop-uim din stiva
{
top--;
}
st[++top]=v[i]; // intoarcere la stanga, adaugam in stiva
}
//Afisare stiva:
fout<<top<<'\n';
for(i=1;i<=top;++i)
fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}