Pagini recente » Cod sursa (job #950795) | Cod sursa (job #2481561) | Cod sursa (job #2824913) | Cod sursa (job #1948487) | Cod sursa (job #1354062)
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int N;
#define MAX 120001
struct Point2D
{
double x,y;
}P[MAX];
int R[MAX];
double crossProd2D(Point2D p1,Point2D p2,Point2D p3)
{
return (p3.y-p2.y)*(p2.x-p1.x) - (p2.y-p1.y)*(p3.x-p2.x);
}
double slope(Point2D p1,Point2D p2)
{
return (p2.y-p1.y)/(p2.x-p1.x);
}
double dist(Point2D p1,Point2D p2)
{
return sqrt((p2.y-p1.y)*(p2.y-p1.y) + (p2.x-p1.x)*(p2.x-p1.x));
}
int main()
{
in>>N;
int i;
for(i=0;i<N;i++)
in>>P[i].x>>P[i].y;
int p=0;
double min=P[0].y;
for(i=1;i<N;i++)
if(P[i].y<min)
{
min=P[i].y;
p=i;
}
else if(P[i].y==min)
if(P[i].x<P[p].x)
p=i;
R[0]=p;
int q,s=p;
int nr=0;
i=0;
R[0]=p;
do
{
q=(s+1)%N;
for(int i=0;i<N;i++)
if(crossProd2D(P[s],P[q],P[i])<0)
q=i;
R[i+1]=q;
s=q;
nr++;
i++;
}while(s!=p);
out<<nr<<'\n';
for(int i=0;i<nr;i++)
out<<P[R[i]].x<<" "<<P[R[i]].y<<'\n';
return 0;
}