Pagini recente » Cod sursa (job #1228694) | Cod sursa (job #2800602) | Cod sursa (job #75727) | Cod sursa (job #1943938) | Cod sursa (job #1525694)
#include <stdio.h>
#include <stdlib.h>
struct punct{
double x, y;
}v[120000];
int conv[120000];
int s[120000], p[120000];
int determinant(int p1, int p2, int p3){
return v[p1].x*v[p2].y+v[p2].x*v[p3].y+v[p3].x*v[p1].y-v[p3].x*v[p2].y-v[p1].x*v[p3].y-v[p2].x*v[p1].y;
}
int sens(int vf){
if(determinant(p[s[vf-2]],p[s[vf-1]],p[s[vf]])<0)
return -1;
return 1;
}
struct dreapta{
double a, b, c;
};
int comp(struct punct p1, struct punct p2){
if(p1.x<p2.x)
return 1;
else if(p1.x>p2.x)
return 0;
else if(p1.y<p2.y)
return 1;
else
return 0;
}
void myqsort( int begin, int end ) {
int aux, b = begin, e = end;
struct punct pivot = v[p[begin + rand() % (end - begin + 1)]];
while ( b <= e ) {
while ( comp(v[p[b]],pivot) ) b++;
while ( comp(pivot,v[p[e]]) ) e--;
if ( b <= e ) {
aux = p[b]; p[b] = p[e]; p[e] = aux;
b++; e--;
}
}
if ( begin < e ) myqsort( begin, e );
if ( b < end ) myqsort( b, end );
}
int main()
{
int n, i, poz, vf;
FILE *fi=fopen("infasuratoare.in", "r"), *fo=fopen("infasuratoare.out", "w");
fscanf(fi, "%d", &n);
//citire
for(i=0;i<n;i++){
fscanf(fi, "%lf%lf", &v[i].x, &v[i].y);
p[i]=i;
}
myqsort(0,n-1);
/*for(u=n-1;u>0;u--){
max=v[p[u]].x;
poz=u;
for(i=0;i<u;i++)
if(v[p[i]].x>max){
max=v[p[i]].x;
poz=i;
}
aux=p[u];
p[u]=p[poz];
p[poz]=aux;
}*/
s[0]=0;
s[1]=1;
vf=1;
for(i=2;i<n;i++){
vf++;
s[vf]=i;
while(vf>1 && sens(vf)==1){
s[vf-1]=s[vf];
vf--;
}
}
poz=0;
for(i=vf;i>=0;i--){
conv[poz]=p[s[i]];
poz++;
}
s[0]=n-1;
s[1]=n-2;
vf=1;
for(i=n-3;i>=0;i--){
vf++;
s[vf]=i;
while(vf>1 && sens(vf)==1){
s[vf-1]=s[vf];
vf--;
}
}
for(i=vf-1;i>0;i--){
conv[poz]=p[s[i]];
poz++;
}
fprintf(fo, "%d", poz);
for(i=0;i<poz;i++)
fprintf(fo, "\n%lf %lf", v[conv[i]].x, v[conv[i]].y);
fclose(fi);
fclose(fo);
return 0;
}