[HDU] 2295 Radar 2점 + 중복 적용
제목 분석: 2점 중복 덮어쓰기...없어지다
코드는 다음과 같습니다.
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define REC( i , A , o ) for ( int i = A[o] ; i != o ; i = A[i] )
const int MAXC = 60 ;
const int MAXR = 60 ;
const int MAXN = 60 ;
const int MAXNODE = 4000 ;
const int INF = 0x3f3f3f3f ;
const double eps = 1e-8 ;
struct Node {
int x , y ;
void input () {
scanf ( "%d%d" , &x , &y ) ;
}
} ;
struct DLX {
int L[MAXNODE] , R[MAXNODE] , U[MAXNODE] , D[MAXNODE] ;
int row[MAXNODE] , col[MAXNODE] ;
int H[MAXR] , S[MAXC] ;
bool vis[MAXC] ;
int deep ;
int size ;
int nv ;
Node a[MAXN] , b[MAXN] ;
double dis[MAXN][MAXN] ;
int n , m , k ;
char s[20] ;
void init () {
CLR ( H , -1 ) ;
FOR ( i , 0 , nv ) {
S[i] = 0 ;
U[i] = D[i] = i ;
L[i] = i - 1 ;
R[i] = i + 1 ;
}
L[0] = nv ;
R[nv] = 0 ;
size = nv ;
deep = INF ;
}
void link ( int r , int c ) {
++ size ;
++ S[c] ;
row[size] = r ;
col[size] = c ;
U[size] = U[c] ;
D[size] = c ;
D[U[c]] = size ;
U[c] = size ;
if ( ~H[r] ) {
L[size] = L[H[r]] ;
R[size] = H[r] ;
L[R[size]] = size ;
R[L[size]] = size ;
}
else
H[r] = L[size] = R[size] = size ;
}
void remove ( int c ) {
REC ( i , D , c ) {
L[R[i]] = L[i] ;
R[L[i]] = R[i] ;
}
}
void resume ( int c ) {
REC ( i , U , c ) {
L[R[i]] = i ;
R[L[i]] = i ;
}
}
int h () {
int cnt = 0 ;
CLR ( vis , 0 ) ;
REC ( i , R , 0 )
if ( !vis[i] ) {
++ cnt ;
vis[i] = 1 ;
REC ( j , D , i )
REC ( k , R , j )
vis[col[k]] = 1 ;
}
return cnt ;
}
int dance ( int d ) {
if ( d + h () > k )
return 0 ;
if ( R[0] == 0 )
return 1 ;
int c = R[0] ;
REC ( i , R , 0 )
if ( S[c] > S[i] )
c = i ;
REC ( i , D , c ) {
remove ( i ) ;
REC ( j , R , i )
remove ( j ) ;
if ( dance ( d + 1 ) )
return 1 ;
REC ( j , L , i )
resume ( j ) ;
resume ( i ) ;
}
return 0 ;
}
double dist ( int i , int j ) {
double x = a[i].x - b[j].x ;
double y = a[i].y - b[j].y ;
return sqrt ( x * x + y * y ) ;
}
int f ( double r ) {
init () ;
FOR ( j , 1 , m )
FOR ( i , 1 , n )
if ( dis[i][j] <= r )
link ( j , i ) ;
return dance ( 0 ) ;
}
void solve () {
scanf ( "%d%d%d" , &n , &m , &k ) ;
nv = n ;
FOR ( i , 1 , n )
a[i].input () ;
FOR ( i , 1 , m )
b[i].input () ;
FOR ( i , 1 , n )
FOR ( j , 1 , m )
dis[i][j] = dist ( i , j ) ;
double l = 0 , r = 1500 ;
while ( r - l > eps ) {
double mid = ( l + r ) / 2 ;
if ( f ( mid ) )
r = mid ;
else
l = mid ;
}
printf ( "%f
" , l ) ;
}
} dlx ;
int main () {
int T ;
scanf ( "%d" , &T ) ;
while ( T -- )
dlx.solve () ;
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.