Pagini recente » Cod sursa (job #2358596) | Cod sursa (job #3174223) | Cod sursa (job #1604411) | Cod sursa (job #3192401) | Cod sursa (job #1238932)
#include <fstream>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int N=1+1e5;
double abs(double a){
return a>-a?a:-a;
}
struct Pct{
double x,y;
} p[N],s[5001];
int t,n;
bool better(Pct a, Pct b){
double f=(b.x-p[1].x)*(a.y-p[1].y),g=(a.x-p[1].x)*(b.y-p[1].y);
if(g-f>0) return true;
if(g-f==0 && (abs(a.x-p[0].x)<abs(b.x-p[0].x) || abs(a.y-p[0].y)<abs(b.y-p[0].y))) return true;
return false;
}
void emsort(int st, int dr){
if(st>=dr) return ;
Pct a;
int i,j;
for(i=j=st ; j<dr ; j++){
if(better(p[j],p[dr])){
a=p[j];
p[j]=p[i];
p[i]=a;
i++;
}
}
a=p[i];
p[i]=p[dr];
p[dr]=a;
emsort(st,i-1);
emsort(i+1,dr);
}
bool bad(Pct a){
return (s[t].x-a.x)*(s[t-1].y-a.y)>=(s[t].y-a.y)*(s[t-1].x-a.x);
}
int main()
{
int z;
in>>n;
in>>p[1].x>>p[1].y;
z=1;
for(int i=2 ; i<=n ; i++){
in>>p[i].x>>p[i].y;
if(p[i].y<p[z].y) z=i;
if(p[i].y==p[z].y && p[i].x<p[z].x) z=i;
}
s[++t]=p[z];
Pct a=p[z];
p[z]=p[1];
p[1]=a;
emsort(2,n);
s[++t]=p[2];
s[++t]=p[3];
for(int i=4 ; i<=n ; i++){
while(bad(p[i]) && t>2){
t--;
}
s[++t]=p[i];
}
out<<t<<'\n';
for(int i=1 ; i<=t ; i++){
out<<s[i].x<<' '<<s[i].y<<'\n';
}
return 0;
}