Pagini recente » Cod sursa (job #2280916) | oni_2012_11-12_ziua_1 | Cod sursa (job #2462168) | Cod sursa (job #618720) | Cod sursa (job #2047507)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define file "infasuratoare"
#define N 120003
using namespace std;
ifstream fin(file".in");
ofstream fout(file".out");
int n;
int stiva[N],len;
bool viz[N];
struct punct{
float x,y;
} A[N];
inline bool cmp(const punct &a,const punct &b)
{
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
inline double plan(punct a,punct b,punct p) //returneaza + daca p se afla in planul pozitiv al dreptei (a,b), - daca este in planul negativ
//si 0 daca este pe dreapta. punctul poate fi adaugat doar daca se afla in planul pozitiv al dreptei.
{
return -( (p.x - a.x)*(b.y-a.y) + (a.y - p.y)*(b.x-a.x) ); //in functie de ecuatia dreptei.
}
void citire()
{
fin>>n;
for(int i=1; i<=n; ++i)
fin>>A[i].x>>A[i].y;
}
void Graham()
{
sort(A+1,A+n+1,cmp);
len = 2;
stiva[1] = 1;
stiva[2] = 2;
viz[2] = 1;
for(int i=3; i<=n; ++i)
{
while(len > 1 && plan(A[stiva[len-1]],A[stiva[len]],A[i]) <= 0)
viz[stiva[len]] = 0, --len; // scoatem elementul din stiva.
stiva[++len] = i;
viz[i] = 1;
}
for(int i=n-1; i>=1; --i)
{
if(viz[i]) continue;
while(plan(A[stiva[len-1]],A[stiva[len]],A[i]) <= 0)
--len;
stiva[++len] = i;
}
}
void afisare()
{
fout<<len-1<<"\n";
for(int i=2; i<=len; ++i)
fout<<fixed<<setprecision(12)<<A[stiva[i]].x<<" "<<A[stiva[i]].y<<"\n";
}
int main()
{
citire();
Graham();
afisare();
fin.close(); fout.close();
return 0;
}