Pagini recente » butoaie | Istoria paginii treapuri | Istoria paginii utilizator/liciu | Castel3 | Cod sursa (job #382258)
Cod sursa(job #382258)
#include<fstream>
#include<iostream>
using namespace std;
struct punct{
double x;
double y;
};
int n,npf;
punct v[120001],pf[120001];
void citire();
void qsort(int st,int dr);
int panta(punct a,punct b);
int directie(punct a,punct b,punct c);
void solve();
int main()
{
citire();
ofstream fout("infasuratoare.out");
punct a=v[1];
int p=1;
for(int i=2;i<=n;i++)
if(v[i].x<a.x)
a=v[i],p=i;
else
if(v[i].x==a.x&&v[i].y<a.y)
a=v[i],p=i;
pf[++npf]=a;
for(int i=p;i<n;i++)
v[i]=v[i+1];
n--;
qsort(1,n);
/*cout<<n<<endl;
for(int i=1;i<=n;i++)
cout<<v[i].x<<" "<<v[i].y<<endl;
*/
pf[++npf]=v[1];
solve();
fout<<npf<<endl;
for(int i=1;i<=npf;i++)
fout<<pf[i].x<<" "<<pf[i].y<<endl;
system("pause");
return 0;
}
void citire()
{
ifstream fin("infasuratoare.in");
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
void qsort(int st,int dr)
{
if(st<dr)
{
int i=st,j=dr,d=0;
punct aux;
while(i<j)
{
if(panta(v[i],v[j])>0)
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
d=1-d;
}
i+=d;
j-=1-d;
}
qsort(st,i-1);
qsort(i+1,dr);
}
}
int directie(punct a,punct b,punct c)
{
double d=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
if(d==0)
return 0;//ininte
if(d>0)
return 1;//stanga
return -1;//dreapta
}
int panta(punct a,punct b)
{
if(((a.y-pf[1].y)*(b.x-pf[1].x))>((a.x-pf[1].x)*(b.y-pf[1].y)))
return 1;
if(((a.y-pf[1].y)*(b.x-pf[1].x))<((a.x-pf[1].x)*(b.y-pf[1].y)))
return 0;
return (a.x-pf[1].x)*(a.x-pf[1].x)+(a.y-pf[1].y)*(a.y-pf[1].y)>(b.x-pf[1].x)*(b.x-pf[1].x)+(b.y-pf[1].y)*(b.y-pf[1].y);
}
void solve()
{
int gata=0;
for(int i=2;i<=n;i++)
{
while(directie(pf[npf-1],pf[npf],v[i])<=0 && npf>2)
npf--;
pf[++npf]=v[i];
}
}