Pagini recente » Cod sursa (job #1672170) | Cod sursa (job #1887737) | Cod sursa (job #2818028) | Cod sursa (job #829239) | Cod sursa (job #278510)
Cod sursa(job #278510)
#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[120001],minn;
int n,h,st[120001],pmin;
void citire () {
fin>>n;
minn.x=15000.0,minn.y=15000.0;
for(int i=1;i<=n;i++) {
fin>>s[i].x>>s[i].y;
if(s[i].y<minn.y || (s[i].y==minn.y && s[i].x<minn.x)) {
minn=s[i];
pmin=i;
}
}
pct aux=s[1];
s[1]=s[pmin];
s[pmin]=aux;
fin.close();
}
float det(pct minn,pct a,pct b) {
return (a.x-minn.x)*(a.y-minn.y)-(b.x-minn.x)*(a.y-minn.y);
}
int cmp(pct a,pct b) {
return det(minn,a,b)>0;
}
void infasuratoare () {
sort(s+2,s+n+1,cmp);
h=2;
st[1]=1;
st[2]=2;
for(int i=3;i<=n;++i) {
while(h>=2 && det(s[st[h]],s[i],s[st[h-1]])<=0)
h--;
st[++h]=i;
}
}
void afisare () {
fout<<h<<"\n";
for(int i=1;i<=h;i++)
fout<<s[st[i]].x<<" "<<s[st[i]].y<<"\n";
fout.close();
}
int main () {
citire();
infasuratoare();
afisare();
return 0;
}