Pagini recente » Cod sursa (job #2325409) | Cod sursa (job #1433228) | Cod sursa (job #501821) | Cod sursa (job #2186275) | Cod sursa (job #915524)
Cod sursa(job #915524)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
struct pct
{
int poz;
double x,y;
}x[100001];
const double prec=pow(10,-12);
int minn=1;
double panta[100001];
pct stiv[100001];
int cur;
int smn;
inline int semn(pct x1, pct x2, pct x3)
{
double det = x1.x*(x2.y-x3.y)+x1.y*(x3.x-x2.x)-x3.x*x2.y+x3.y*x2.x;
if(det>prec)
return 1;
if(det<-prec)
return -1;
if(det<prec)
return 0;
}
bool cmp(const pct x1,const pct x2)
{
if(panta[x1.poz]-panta[x2.poz]>prec)
return true;
else if(abs(panta[x1.poz]-panta[x2.poz])<prec)
if(x1.x-x2.x>prec)
return true;
else if(abs(x1.x-x2.x)<prec)
if(x1.y-x2.y<-prec)
return true;
else return false;
}
inline double dist(int x1, int x2)
{
return sqrt((x[x1].x-x[x2].x)*(x[x1].x-x[x2].x)+(x[x1].y-x[x2].y)*(x[x1].y-x[x2].y));
}
void citire()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lf%lf",&x[i].x,&x[i].y);
x[i].poz=i;}
fclose(stdin);
}
void stab_pornire()
{
for(int i=2;i<=n;++i)
if(x[i].y-x[minn].y<-prec)
minn=i;
else if(abs(x[i].y-x[minn].y)<prec)
if(x[i].x-x[minn].x<-prec)
minn=i;
stiv[++cur]=x[minn];
}
void pante()
{
for(int i=1;i<=n;++i)
if(x[i].poz!=stiv[1].poz&&abs(x[i].y-stiv[1].y)>prec)
panta[i]=((x[i].x-x[minn].x)/dist(minn,i));
else if(x[i].poz!=stiv[1].poz&&abs(x[i].y-stiv[1].y)<prec){
panta[i]=1;
if(x[i].x>stiv[2].x)
stiv[2]=x[i];
}
}
void infconv()
{
int i;
cur=3;
int p=0;
for(int i=1;i<=n;++i)
if(stiv[2].poz==x[i].poz){
p=i;break;}
if(p==0){
stiv[2]=x[1];
p=1;}
stiv[3]=x[p+1];
smn=semn(stiv[1],stiv[2],stiv[3]);
for(int i=p+2;i<=n;++i)
{
if(x[i].poz!=stiv[1].poz){
if(smn!=semn(stiv[cur-1],stiv[cur],x[i]))
stiv[cur]=x[i];
else
stiv[++cur]=x[i];
}
}
}
void afisare()
{
freopen("infasuratoare.out","w",stdout);
printf("%d\n",cur);
for(int i=1;i<=cur;++i)
printf("%lf %lf\n",stiv[i].x,stiv[i].y);
}
int main()
{
citire();
stab_pornire();
pante();
sort(x+1,x+n+1,cmp);
infconv();
afisare();
return 0;
}