2712963_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include "stdio.h"
#include "math.h"
#define size 100
#define printg(a,b,c,d) printf("%g %g %g %g\n",a,b,c,d )
#define printlf(a,b,c,d) printf("%.4lf %.4lf %.4lf %.4lf\n", a,b,c,d )
typedef double DEC;
typedef int INT;
typedef struct Coordinate{
        DEC x, y;     
}COOR;
typedef struct line{
        INT a, b, c;     
        DEC d, dirx, diry;   
}LINE;

COOR point[ size ], corner[ size ], circle[ 2 ];
LINE wall[ size ];
INT n, r, flag[ size ];
DEC PI;

void input(){
     INT i;
     scanf("%d%d", &n, &r );
     for ( i = 0; i < n; i++ ){
         scanf("%lf%lf", &(point[ i ].x), &(point[ i ].y) );
     }     
}

void InitLine(){
     INT i, s, e;
     DEC t;
     
     for ( s = 0; s < n; s++ ){
         e = s + 1 < n ? s + 1 : 0;
         wall[ s ].a = point[ e ].y - point[ s ].y;
         wall[ s ].b = point[ s ].x - point[ e ].x;
         wall[ s ].c = -point[ e ].x * wall[ s ].a -point[ e ].y * wall[ s ].b;
         wall[ s ].d = sqrt( wall[ s ].a * wall[ s ].a + wall[ s ].b * wall[ s ].b );
         wall[ s ].dirx = -wall[ s ].b / wall[ s ].d;
         wall[ s ].diry = wall[ s ].a / wall[ s ].d; 
     }
          
}
DEC ABS( DEC x ){
    return x >= 0 ? x : -x;
}
DEC distance( COOR p, LINE l ){
    return ABS( p.x * l.a + p.y * l.b + l.c ) / l.d;
}
DEC Formal( DEC x ){
    INT a , flag = 1;
    if ( x < 0 ){
         flag = -1;
         x *= -1;   
    }
    a = ( INT ) ( x * 10000 );
    x = a / 10000;
    x += a % 10000 * 0.0001;
    return flag * x;
}
void CorssPoint( INT e ){
     INT s, i, j, a[ 2 ], b[ 2 ];
     DEC dx, dy, c[ 2 ];
     s = e - 1 >= 0 ? e - 1 : n - 1;
     dx = wall[ e ].dirx - wall[ s ].dirx;dy = wall[ e ].diry - wall[ s ].diry;
     a[ 0 ] = wall[ s ].a;a[ 1 ] = wall[ e ].a;
     b[ 0 ] = wall[ s ].b;b[ 1 ] = wall[ e ].b;
     //printf("%d : %lf %lf\n", e, dx, dy );
     for ( i = -1; i <= 1; i += 2 ){
         c[ 0 ] = wall[ s ].c + i * r * wall[ s ].d; 
         for ( j = -1; j <= 1; j+= 2 ){
             c[ 1 ] = wall[ e ].c + j * r * wall[ e ].d;
             corner[ e ].x = (c[0]*b[1]-c[1]*b[0])/(a[1]*b[0]-a[0]*b[1]);
             corner[ e ].y = (c[0]*a[1]-c[1]*a[0])/(a[0]*b[1]-a[1]*b[0]);
             //printf("%lf %lf\n", corner[ e ].x, corner[ e ].y );
             //printf("%lf %lf\n\n", corner[ e ].x - point[ e ].x, corner[ e ].y - point[ e ].y );
             if ( dx * ( corner[ e ].x - point[ e ].x ) >= 0 && dy * (corner[ e ].y - point[ e ].y) >= 0 ){
                  i = j = 1;
             }
         }
     }
     
     corner[ e ].x = Formal( corner[ e ].x );
     corner[ e ].y = Formal( corner[ e ].y );
     if ( distance( corner[ e ], wall[ e ] ) >= r && distance( corner[ e ], wall[ s ] ) >= r ) return;
     corner[ e ].x += 0.0001;
     if ( distance( corner[ e ], wall[ e ] ) >= r && distance( corner[ e ], wall[ s ] ) >= r ) return;
     corner[ e ].x -= 0.0001;corner[ e ].y += 0.0001;
     
}

void InitCorner(){
     INT i, j;
     DEC t;
     for ( i = 0; i < n; i++ ){
         CorssPoint( i );
         flag[ i ] = 1;        
         for ( j = 0; j < n; j++ ){
             t = distance( corner[ i ], wall[ j ] );
             if ( t < r ){
                  //printf("%d %d %d %lf\n", wall[ j ].a, wall[j].b,wall[j].c, wall[j].d );
                  flag[ i ] = 0;
                  break;
             }
         }
     }
     
}

DEC square( DEC x ){
    return x * x;
}

void FindLongest(){
     INT i, j;
     DEC d = 0, t;
     
     for ( i = 0; i < n; i++ ){
         if ( !flag[ i ] ) continue;
         for ( j = i + 1; j < n; j++ ){
             if ( !flag[ j ] ) continue;
             t = square( corner[ i ].x - corner[ j ].x ) + square( corner[ i ].y - corner[ j ].y );
             if ( t > d ){
                  circle[ 0 ] = corner[ i ];
                  circle[ 1 ] = corner[ j ];   
                  d = t;
             }
         }
     }     
}



void solve(){
     INT i;
     PI = 2 * asin( 1 );
     InitLine();
     
     //for ( i = 0; i < n; i++ ) printf("%d %d %d %lf\n", wall[i].a,wall[i].b,wall[i].c,wall[i].d);
     //for ( i = 0; i < n; i++ ) printf("%lf %lf\n", wall[ i ].dirx, wall[ i ].diry );
     InitCorner();
     //for ( i = 0 ; i < n ;i++ ) printf("%lf %lf\n", corner[ i ].x, corner[ i ].y );
     //for ( i = 0; i < n ;i++ ) printf("%d ", flag[ i ] ); puts("");
     FindLongest();   
     /*for ( i = 0; i < 2; i++ ){
         circle[ i ].x = Formal( circle[ i ].x );
         circle[ i ].y = Formal( circle[ i ].y );
     }*/
     printg( circle[ 0 ].x, circle[ 0 ].y, circle[ 1 ].x, circle[ 1 ].y );
}

int main(){
    input();
    solve();
    system("pause");
    return 0;
}