Pagini recente » Cod sursa (job #2368058) | Cod sursa (job #2547435) | Cod sursa (job #169139) | Cod sursa (job #87658) | Cod sursa (job #1676351)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define pdd pair<double, double>
#define x first
#define y second
#define mkp make_pair
#define nMax 120003
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, top;
pdd Pct[nMax], Stck[nMax];
void read()
{
double a, b;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>a>>b;
Pct[i]=mkp(a, b);
}
}
double cross_product(const pdd& A, const pdd& B, const pdd& C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline bool cmp(const pdd& A, const pdd& B)
{
return cross_product(Pct[1], A, B)<0;
}
void sort_points()
{
int poz=1;
for(int i=2;i<=n;i++)
{
if(Pct[i]<Pct[poz])
poz=i;
}
swap(Pct[1], Pct[poz]);
sort(Pct+2, Pct+n+1, cmp);
}
void solve()
{
sort_points();
Stck[++top]=Pct[1];
Stck[++top]=Pct[2];
for(int i=3;i<=n;i++)
{
while(top>=2 && cross_product(Stck[top-1], Stck[top], Pct[i])>0)
top--;
Stck[++top]=Pct[i];
}
}
void write()
{
fout<<top<<'\n';
for(int i=top;i>=1;i--)
fout<<fixed<<setprecision(6)<<Stck[i].x<<" "<<Stck[i].y
<<'\n';
}
int main()
{
read();
solve();
write();
return 0;
}