Pagini recente » Cod sursa (job #2414152) | Cod sursa (job #1940170) | Cod sursa (job #462728) | Cod sursa (job #23693) | Cod sursa (job #1332667)
#include <fstream>
#include <list>
#include <algorithm>
#include <cmath>
#define Nmax 120005
#define INF 1000000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
} V[Nmax],fr;
list<punct> li;
void Citire();
double Aria(double x0, double x1, double x2, double y0, double y1, double y2);
int compare(punct a, punct b);
void ParcurgereLista();
int N;
void Afisare();
int main()
{
Citire();
sort(V+2,V+N+1,compare);
ParcurgereLista();
Afisare();
return 0;
}
void Citire()
{
int i;
fin>>N;
int poz;
fr.x = fr.y = INF;
for(i=1;i<=N;i++)
{
fin>>V[i].x>>V[i].y;
if(V[i].x<fr.x)
fr=V[i], poz=i;
else if(V[i].x== fr.x && V[i].y< fr.y)
fr.y=V[i].y, poz=i;
}
swap(fr,V[poz]);
}
int compare(punct a, punct b)
{
return( Aria(a.x,fr.x,b.x, a.y, fr.y,b.y)>0);
}
double Aria(double x0, double x1, double x2, double y0, double y1, double y2)
{
return (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
}
void ParcurgereLista()
{
int i;
for(i=1;i<=N;i++)
li.push_back(V[i]);
list<punct>::iterator it0,it1,it2;
it0=it1=it2=li.begin();
it1++; it2++; it2++;
do
{
if(Aria((*it0).x, (*it1).x,(*it2).x,(*it0).y,it1->y,it2->y)<0)
{
it0++; it1++; it2++;
}
else
{
li.erase(it1); it1=it0; it0--;
}
}while(it2!=li.end());
}
void Afisare()
{
fout<<li.size()<<'\n';
list<punct>::iterator it;
fout<<fixed;
for(it=li.begin(); it!=li.end(); ++it)
fout<<(it->x)<<" "<<(it->y)<<'\n';
}