Pagini recente » Cod sursa (job #689414) | Cod sursa (job #1675670) | Cod sursa (job #306364) | Cod sursa (job #2549524) | Cod sursa (job #2722648)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct infasuratoare
{
double x,y;
}v[120100],sol[120100];
int compare(infasuratoare A, infasuratoare B)
{
return ((A.x-v[1].x)*(B.y-v[1].y) > (B.x-v[1].x)*(A.y-v[1].y));
}
int viraj_dreapta(infasuratoare A, infasuratoare B, infasuratoare C)
{
/// A.x A.y 1
/// B.x B.y 1
/// C.x C.y 1
return ((A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - C.y*A.x - B.x*A.y)<0);
}
int n,i,minix,T,punct=INT_MAX,miniy=INT_MAX;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x<minix)
{
minix=v[i].x;
miniy=v[i].y;
punct=i;
}
else if(v[i].x==minix)
{
if(v[i].y<miniy)
{
miniy=v[i].y;
punct=i;
}
}
}
swap(v[1],v[punct]);
sort(v+2,v+n+1,compare);
T=2;
sol[1]=v[1];sol[2]=v[2];
for(i=3;i<=n;i++)
{
while(T>2 && viraj_dreapta(sol[T-1],sol[T],v[i]))T--;
T++;sol[T]=v[i];
}
g<<T<<'\n';
for(i=1;i<=T;i++)
g<<fixed<<setprecision(12)<<sol[i].x<<" "<<sol[i].y<<'\n';
return 0;
}