Pagini recente » Istoria paginii runda/inca_vacanta_x | Cod sursa (job #26369) | Istoria paginii runda/problemebarajgimnaziu | Cod sursa (job #1731482) | Cod sursa (job #1918507)
#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 (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.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;
}