Pagini recente » Cod sursa (job #2750922) | Cod sursa (job #323595) | Cod sursa (job #913304) | Cod sursa (job #657700) | Cod sursa (job #1871313)
#include <algorithm>
#include <iomanip>
#include <fstream>
#define NMAX 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
long long n,up;
struct coord{
long double x;
long double y;
} v[NMAX],stiv[NMAX];// vector de puncte, retine coordonata x si coordonata y
long double det(coord a, coord b, coord c) // calculez determinantul si afiseaza semnul lui
{
return ((a.x*b.y)+(b.x*c.y)+(a.y*c.x)-(c.x*b.y)-(c.y*a.x)-(b.x*a.y));
}
int cmp(coord a,coord b) // compara doua sructuri. Nu imi merge == la structuri (De cercetat)
{
if(a.x==b.x && a.y==b.y)
return 1;
return 0;
}
long long poz(long long p,long long u) // QUICKSORT (SORTEAZA DUPA pozitia cu punctul de start)
{
coord piv,c;
piv=v[p];
while(p<u)
{
if(det(v[1],v[p],v[u])<0)
{
c=v[p];
v[p]=v[u];
v[u]=c;
}
if(cmp(v[p],piv))
u--;
else
p++;
}
return p;
}
void quick(long long p,long long u)
{
long long k;
if(p<u)
{
k=poz(p,u);
quick(p,k-1);
quick(k+1,u);
}
} // FINAL QUICKSORT
void cit()
{
int i;
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x < v[1].x ||(v[i].x==v[1].x && v[i].y<v[1].y))
swap(v[1],v[i]); //punem pe prima pozitie elementul cu x cel mai mic (Cel mai din stanga)
}
}
void infasur()
{
int i;
quick(2,n);// primul element ramane unde e
stiv[1]=v[1];
stiv[2]=v[2];
up=2;
for(i=3;i<=n;i++)
{
while(up>=2 && det(stiv[up-1],stiv[up],v[i])<0)
up--;
up++;
stiv[up]=v[i];
}
}
void af_rezultat()
{
int i;
g<<up<<'\n';
for(i=1;i<=up;i++)
{
g<<fixed<<setprecision(6)<<stiv[i].x<<' '<<stiv[i].y<<'\n';
}
}
int main()
{
int i;
cit();
infasur();
af_rezultat();
return 0;
}