Pagini recente » Cod sursa (job #1827250) | Cod sursa (job #11017) | Cod sursa (job #2205359) | Cod sursa (job #2658894) | Cod sursa (job #897120)
Cod sursa(job #897120)
#include<stdio.h>
#include<algorithm>
#define maxn 120005
#define inf (1LL<<62)
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
int n;
int st[maxn];
struct pct{
double x,y;
double ctg;
}A[maxn];
struct cmp{
inline bool operator () ( const pct &a , const pct &b ){
return a.ctg > b.ctg;
}
};
double det ( const pct &a , const pct &b , const pct &c ){
double d = (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y);
return d;
}
void infasuratoare ( int &n , pct *S ){
double xmin = inf,ymin = inf; int poz = 0;
for ( int i = 1 ; i <= n ; ++i ){
if ( S[i].y < ymin || (S[i].y == ymin && S[i].x < xmin ) ){
ymin = S[i].y;
xmin = S[i].x;
poz = i;
}
}
swap(S[1],S[poz]); S[1].x = S[1].y = 0;
for ( int i = 2 ; i <= n ; ++i ){
S[i].x -= xmin; S[i].y -= ymin;
S[i].ctg = S[i].x/S[i].y;
}
sort(S+2,S+n+1,cmp());
for ( int i = 1 ; i <= n ; ++i ){
while ( st[0] > 1 && det(S[i],S[st[st[0]]],S[st[st[0]-1]]) > 0 ){
st[st[0]--] = 0;
}
st[++st[0]] = i;
}
for ( int i = 1 ; i <= st[0] ; ++i ){
S[i] = S[st[i]];
S[i].x += xmin; S[i].y += ymin;
}
for ( int i = st[0]+1 ; i <= n ; ++i ) S[i].x = S[i].y = S[i].ctg = 0;
n = st[0];
}
int main () {
fscanf(f,"%d",&n);
for ( int i = 1 ; i <= n ; ++i ){
fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
}
infasuratoare(n,A);
fprintf(g,"%d\n",n);
for ( int i = 1 ; i <= n ; ++i ){
fprintf(g,"%lf %lf\n",A[i].x,A[i].y);
}
fclose(f);
fclose(g);
return 0;
}