Pagini recente » Cod sursa (job #134345) | Cod sursa (job #180897) | Cod sursa (job #2703040) | Cod sursa (job #1287948) | Cod sursa (job #1134590)
#include <iostream>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct
{
double x,y;
double u;
};
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
punct p[120010];
int pos;
punct pmin;
double x,y;
int nr;
int st[120010];
bool cmp(punct a, punct b)
{
return a.u>b.u;
}
void citire()
{
int i;
in>>n;
in>>p[1].x>>p[1].y;
pmin=p[1];
pos=1;
x=p[1].x;
y=p[1].y;
for(i=2;i<=n;i++)
{
in>>p[i].x>>p[i].y;
/*if(p[i].x<=pmin.x)
{
if(p[i].x<pmin.x)
{
pmin=p[i];
pos=i;
}
else if(p[i].y<pmin.y)
{
pmin=p[i];
pos=i;
}
}*/
if(p[i].x<x)
x=p[i].x;
if(p[i].y<y)
y=p[i].y;
if(p[i].x<=pmin.x)
if(p[i].x<pmin.x||p[i].y<pmin.y)
{
pmin=p[i];
pos=i;
}
}
p[pos]=p[n];
p[n]=pmin;
x--;
y--;
for(i=1;i<=n;i++)
{
p[i].x-=x;
p[i].y-=y;
p[i].u=atan2(p[i].y,p[i].x);
}
sort(p+1,p+n,cmp);
/*for(i=1;i<=n;i++)
out<<p[i].x<<' '<<p[i].y<<' '<<p[i].u<<'\n';*/
}
double det(punct a, punct b, punct c)
{
/*
|xa ya 1|
|xb yb 1| = D
|xc yc 1|
*/
double D=0;
D=(a.x*b.y)+(b.x*c.y)+(c.x*a.y)-(b.y*c.x)-(c.y*a.x)-(a.y*b.x);
return D;
}
void infasuratoare()
{
st[1]=n;
st[2]=1;
int i,k=2;
for(i=2;i<n;i++)
{
while(det(p[st[k-1]],p[i],p[st[k]])<0)
k--;
k++;
st[k]=i;
}
out<<k<<'\n';
out<<fixed<<setprecision(6);
for(i=k;i;i--)
out/*<<setprecision(6)*/<<p[st[i]].x+x<<' '<<p[st[i]].y+y<<'\n';
}
void test()
{
p[1].x=0;
p[1].y=2;
p[2].x=2;
p[2].y=0;
p[3].x=0;
p[3].y=0;
cout<<det(p[1],p[2],p[3]);
}
int main()
{
citire();
infasuratoare();
//test();
return 0;
}