Pagini recente » Cod sursa (job #1897870) | Cod sursa (job #2137862) | Cod sursa (job #2745638) | Cod sursa (job #76541) | Cod sursa (job #1082516)
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#define NMAX 120005
#define x first
#define y second
FILE *fout;
using namespace std;
ifstream fin("infasuratoare.in");
//ofstream fout("infasuratoare.out");
typedef pair<double, double> Point;
Point v[NMAX];
Point stack[NMAX];
int n;
void read()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
double cross_product(Point A, Point B, Point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int comp(Point p1, Point p2)
{
return cross_product(v[1],p1,p2)<0;
}
void sortare()
{
int pos=1;
for(int i=2;i<=n;i++)
if(v[i]<v[pos])
pos=i;
swap(v[1],v[pos]);
sort(v+2,v+n+1,comp);
}
void solve()
{
sortare();
stack[1]=v[1];
stack[2]=v[2];
int head=2;
for(int i=3;i<=n;i++)
{
while(head>=2 && cross_product (stack[head-1],stack[head], v[i])>0)
--head;
stack[++head]=v[i];
}
// fout<<head<<"\n";
fout=fopen("infasuratoare.out","w");
fprintf(fout,"%d\n",head);
for (int i = head; i >= 1; --i)
fprintf(fout,"%0.6lf %0.6lf\n",stack[i].x,stack[i].y);
//fout << setprecision(9) << stack[i].x << " " << stack[i].y << "\n";
}
int main()
{
read();
solve();
}