Pagini recente » Cod sursa (job #1824024) | Cod sursa (job #2657489) | Cod sursa (job #1521855) | Cod sursa (job #2904125) | Cod sursa (job #278435)
Cod sursa(job #278435)
#include<fstream>
#include<iostream>
#include<math.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct pct {
float x,y,d,c;
};
pct s[10000],st[10000],minn;
int n,h;
void citire () {
fin>>n;
for(int i=0;i<n;i++)
fin>>s[i].x>>s[i].y;
fin.close();
}
float dist (pct a,pct b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int determinant (pct a,pct b,pct c) {
return (a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-c.y*a.x-a.y*b.x);
}
void minim () {
minn.x=10000.0,minn.y=10000.0;
for(int i=0;i<n;i++) {
if(s[i].y<minn.y)
minn=s[i];
else
if(s[i].y==minn.y)
if(s[i].x<minn.x)
minn=s[i];
}
}
void afldist () {
minim();
for(int i=0;i<n;i++)
s[i].d=dist(minn,s[i]);
}
void coss () {
afldist();
for(int i=0;i<n;i++)
s[i].c=(float)((minn.x-s[i].x)/(minn.y-s[i].y));
}
void interschimbare () {
coss();
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++) {
if(s[i].c>s[j].c) {
pct aux=s[i];
s[i]=s[j];
s[j]=aux;
}
else {
if(s[i].c==s[j].c)
if(s[i].d>s[j].d) {
pct aux=s[i];
s[i]=s[j];
s[j]=aux;
}
}
}
}
void stergere () {
for(int i=0;i<n-1;i++) {
if(s[i].c==s[i+1].c) {
for(int j=i+2;j<n;j++)
s[j-1]=s[j];
n--;
}
}
}
void form () {
// stergere();
st[h++]=s[0];
st[h++]=s[1];
for(int i=2;i<n;i++)
if(determinant(st[h-2],st[h-1],s[i])<0)
st[h++]=s[i];
else
st[h-1]=s[i];
}
void afisare () {
fout<<h<<"\n";
fout<<st[0].x<<" "<<st[0].y<<"\n";
for(int i=h-1;i>=1;i--)
fout<<st[i].x<<" "<<st[i].y<<"\n";
fout.close();
}
int main () {
citire();
interschimbare();
form();
afisare();
return 0;
}