Pagini recente » Borderou de evaluare (job #3308851) | Cod sursa (job #1149373) | Cod sursa (job #1790557) | Cod sursa (job #1550021) | Cod sursa (job #3346173)
#include <bits/stdc++.h>
#define NMAX 120002
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N,M,start;
struct punct
{
double x,y;
} v[NMAX],hull[NMAX];
double arie(punct A, punct B, punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool cmp(punct A, punct B)
{
double val=arie(v[start],A,B);
if(val==0)
{
double d1=(A.x-v[start].x)*(A.x-v[start].x)+(A.y-v[start].y)*(A.y-v[start].y);
double d2=(B.x-v[start].x)*(B.x-v[start].x)+(B.y-v[start].y)*(B.y-v[start].y);
return d1<d2;
}
return val>0;
}
void citire()
{
fin>>N;
for(int i=1; i<=N; i++)
{
fin>>v[i].x>>v[i].y;
}
}
int main()
{
citire();
start=1;
for(int i=2; i<=N; i++)
{
if(v[i].x<v[start].x || (v[i].x==v[start].x && v[i].y<v[start].y))
{
start=i;
}
}
M=0;
swap(v[1],v[start]);
start=1;
sort(v+2,v+N+1,cmp);
hull[++M]=v[1];
hull[++M]=v[2];
for(int i=3; i<=N; i++)
{
while(M>=2 && arie(hull[M-1],hull[M],v[i])<=0)
{
M--;
}
hull[++M]=v[i];
}
fout<< M << "\n";
for(int i=1; i<=M; i++)
{
fout<< fixed << setprecision(6) << hull[i].x << " " << hull[i].y << "\n";
}
return 0;
}