Pagini recente » Cod sursa (job #1190480) | Cod sursa (job #2767398) | Cod sursa (job #21328) | Cod sursa (job #1019119) | Cod sursa (job #3149930)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int nm=120001;
struct coord{double x,y;};
stack <coord> stiva, af;
coord p[nm], /// lista de puncte
p0 ; /// punctul in functie de care se face sortarea tuturor punctelor
int n, i, j, pmi, m;
/// ret 0 daca punctele sunt coliniare, 1 daca sunt in ordine inversa trigonometrica (ceas), 2 altfel
int orientare(coord p, coord q, coord r)
{
double x = (q.y-p.y)*(r.x-q.x) - (q.x-p.x)*(r.y-q.y);
if(x==0)return 0;
if(x>0)return 1;
return 2;
}
/// returneaza patratul distantei intre doua puncte
double dist(coord p, coord q)
{
return (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y);
}
int operator<(coord p, coord q)
{
int o=orientare(p0, p, q);
if(o==2)return 1;
if(o==1)return 0;
return dist(p0,q)>=dist(p0,p);
}
/// returneaza al doilea element din stiva
coord stivaDoi(stack <coord> s)
{
coord vf = s.top();
s.pop();
coord doi=s.top();
s.push(vf);
return doi;
}
int main()
{
fin >> n;
for(i=1; i<=n; i++)
fin >> p[i].x >> p[i].y;
/// caut punctul de minim, daca-s mai multe pe cel mai din stanga
pmi = 1;
for(i=2; i<=n; i++)
if(p[i].y<p[pmi].y || (p[i].y==p[pmi].y && p[i].x<p[pmi].x))pmi = i;
/// pun punctul la inceput
swap(p[1],p[pmi]);
p0=p[1];
sort(p+2, p+n+1);/// sortez restul punctelor
m=1; /// modific lista de puncte, si psatrez doar pe cele care merita
for(i=2; i<=n; i++)
{
//while(i<n && orientare(p0, p[i], p[i+1])==0)i++;
m++;
p[m] = p[i];
}
// cout << m << "\n";
//for(i=1; i<=m; i++) cout << p[i].x << " " << p[i].y << "\n";
if(m<3)cout << "Nu merge";
stiva.push(p[1]); stiva.push(p[2]); stiva.push(p[3]);
for(i=4; i<=m; i++)
{
while(stiva.size()>1 && orientare(stivaDoi(stiva), stiva.top(), p[i])==1)
{stiva.pop();}
stiva.push(p[i]);
}
while(!stiva.empty())
{
coord a=stiva.top();
stiva.pop(); af.push(a);
//cout << a.x << " " << a.y << "\n";
}
fout << af.size() << "\n";
fout << setprecision(6) << fixed;
while(!af.empty())
{
coord a=af.top();
af.pop();
fout << a.x << " " << a.y << "\n";
}
return 0;
}