Pagini recente » Cod sursa (job #178932) | Cod sursa (job #2022729) | Cod sursa (job #3244311) | Cod sursa (job #619048) | Cod sursa (job #2003621)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct {
float x,y,unghi;
} a[120001],S[120001];
int n,vf;
bool cmp(Punct x,Punct y)
{
return x.unghi<y.unghi;
}
void Primul()
{
for(int i=2;i<=n;++i)
if(a[i].x<a[1].x)
swap(a[i],a[1]);
else if(a[i].x==a[1].x && a[i].y<a[1].y )
swap(a[i],a[1]);
}
void Sortare()
{
for(int i=2;i<=n;++i)
a[i].unghi=atan(a[i].y/a[i].x);
sort(a+2,a+1+n,cmp);
}
void PUSH(Punct P)
{
vf++;
S[vf]=P;
}
void POP()
{
vf--;
}
float Produs(Punct P1, Punct P2,Punct P3)
{
return (P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y);
}
int main()
{
f>>n;
for(int i=1;i<=n;++i)
f>>a[i].x>>a[i].y;
Primul();
Sortare();
vf=0;
PUSH(a[1]);
PUSH(a[2]);
for(int i=3;i<=n;++i)
{
float o;
o=Produs(S[vf-1],S[vf],a[i]);
if(o==0)
{
POP();
PUSH(a[i]);
}
else
if(o>0)
PUSH(a[i]);
else
{
while(vf>1 && o<=0)
{
POP();
o=Produs(S[vf-1],S[vf],a[i]);
}
PUSH(a[i]);
}
}
g<<vf<<'\n';
for(int i=1;i<=vf;++i)
g<<fixed<<setprecision(6)<<S[i].x<<" "<<S[i].y<<'\n';
return 0;
}