Pagini recente » Cod sursa (job #2923199) | Cod sursa (job #3173997) | Cod sursa (job #2707392) | Cod sursa (job #2465034) | Cod sursa (job #1355267)
#include<iostream>
#include<fstream>
#include<iomanip>
#include<math.h>
#include<algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int N;
#define MAX 120002
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);
}
struct compare
{
bool operator() (Point2D p1,Point2D p2)
{
return crossProd2D(P[1],p1,p2)>0;
}
}comp;
int main()
{
in>>N;
int i;
for(i=1;i<=N;i++)
in>>P[i].x>>P[i].y;
int p=1;
double min=P[1].y;
for(i=2;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;
swap(P[1],P[p]);
sort(P+2,P+N+1,comp);
R[1]=1;
R[2]=2;
int t=2;
for(int i=3;i<=N;i++)
{
while(t>=2 && crossProd2D(P[R[t-1]],P[R[t]],P[i])<0)
t--;
R[++t]=i;
}
out<<t<<'\n';
out<<setprecision(9)<<fixed;
for(int i=1;i<=t;i++)
out<<P[R[i]].x<<" "<<P[R[i]].y<<'\n';
return 0;
}