Pagini recente » Cod sursa (job #454004) | Cod sursa (job #696780) | Cod sursa (job #1711816) | Cod sursa (job #818713) | Cod sursa (job #1918537)
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 120001
#define inf 1000000001
using namespace std;
int N;
struct point {double x,y;} P[NMAX],REZ[NMAX];
double xmin=inf,ymin=inf;int imin,p=1,u=1;
void citire()
{
ifstream fin("infasuratoare.in");
fin>>N;
for(int i=1;i<=N;i++)
{
fin>>P[i].x>>P[i].y;
if(P[i].x<xmin)
{
xmin=P[i].x;
ymin=P[i].y;
imin=i;
}
else
if(xmin==P[i].x&&ymin>P[i].y)
{
xmin=P[i].x;
ymin=P[i].y;
imin=i;
}
}
}
double det(point A,point B,point C)
{
return A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-A.x*C.y-B.x*A.y;
}
//A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-A.x*C.y-B.x*A.y;
//(A.x-B.x)*(C.y-B.y)-(A.y-B.y)*(C.x-B.x)
int cmp(point A,point B)
{
return det(P[1],A,B)<0;
}
void rez()
{
swap(P[1],P[imin]);
sort(P+2,P+N+1,cmp);
REZ[1]=P[1];
REZ[2]=P[2];
u=2;
for(int i=3;i<=N;i++)
{
while((det(REZ[u-1],REZ[u],P[i])>0)&&u>2)
u--;
REZ[++u]=P[i];
}
ofstream fout("infasuratoare.out");
fout<<u<<endl;
for(int i=1;i<=u;i++)
fout<<REZ[i].x<<" "<<REZ[i].y<<endl;
}
int main()
{
citire();
rez();
return 0;
}