Pagini recente » Cod sursa (job #3263702) | Cod sursa (job #3004452) | Borderou de evaluare (job #2620199) | Cod sursa (job #2761023) | Cod sursa (job #700544)
Cod sursa(job #700544)
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define MaxN 100
#define INF 100000
fstream f(IN, ios::in), g(OUT, ios::out);
int n, i, poz, A[MaxN], nr;
double pxmin, pymin;
struct PUNCT{
double x;
double y;
double panta;
}point[MaxN];
double PANTA(int X)
{
if(point[0].x == point[X].x) return INF;
else return (point[X].y-point[0].y)/(point[X].x-point[0].x);
}
bool cmp(PUNCT X, PUNCT Y)
{
return (X.panta<Y.panta);
}
double DETERMINANT(int x1,int y1,int z1)
{
double s1=0;
s1+=(point[x1].x*point[y1].y);
s1+=(point[y1].x*point[z1].y);
s1+=(point[x1].y*point[z1].x);
s1-=(point[y1].y*point[z1].x);
s1-=(point[x1].x*point[z1].y);
s1-=(point[y1].x*point[x1].y);
return s1;
}
int main()
{
f>>n;
f>>point[1].x>>point[1].y;
pxmin=point[1].x; pymin=point[1].y; poz=1;
for(i=2; i<=n; i++){
f>>point[i].x>>point[i].y;
if(point[i].x<pxmin){
pxmin=point[i].x; pymin=point[i].y; poz=i;
}
else if(point[i].x==pxmin && point[i].y<pymin){
pxmin=point[i].x; pymin=point[i].y; poz=i;
}
}
point[0]=point[poz];
point[poz]=point[n];
n--;
for(i=1; i<=n; i++)
point[i].panta=PANTA(i);
sort(point+1, point+n+1, cmp);
// for(i=1; i<=n; i++)
// g<<point[i].x<<" "<<point[i].y<<" "<<point[i].panta<<"\n";
A[0]=0; A[1]=1; nr=1;
for(i=2; i<=n; i++)
{
while(nr>0 && DETERMINANT(A[nr-1],A[nr],i)<0)
nr--;
A[++nr]=i;
}
g<<nr+1<<"\n";
for(i=0; i<=nr; i++)
g<<fixed<<setprecision(12)<<point[A[i]].x<<" "<<point[A[i]].y<<"\n";
}