UVA10641 照亮体育馆 Barisal Stadium

标签：const point int double ans UVA10641 vec Stadium Barisal

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define vec point


const double eps = 1e-6 ;
const int N = 1000 + 11 ;


struct point
{
	double x , y ;
	point ( double xx = 0 , double yy = 0 ) : x ( xx ) , y ( yy ) {}
} p [ N ] ;
point operator - ( const point & x , const point & y ) { 
	return point ( x . x - y . x , x . y - y . y ) ; 
}
struct light {
	int l , r , cost ;
} a [ N ] ;
bool vis [ N ] ;
int f [ N * 2 ] ;
int n , m ;


double dot ( vec x , vec y ) { return x . x * y . x + x . y * y . y ; }
double across ( vec x , vec y ) { return x . x * y . y - x . y * y . x ; }


void work ( vec x , int now ) {
	memset ( vis , false , sizeof ( vis ) ) ;
	for ( int i = 1 ; i <= n ; i ++ ) {
		if ( across ( p [ i ] - x , p [ i + 1 ] - x ) < - eps ) vis [ i ] = 1 ;
	}
	if ( vis [ 1 ] and vis [ n ] ) {
		int &l = a [ now ] . l ;
		int &r = a [ now ] . r ;
		l = n ; r = 1 ;
		while ( vis [ l - 1 ] == true ) l -- ;
		while ( vis [ r + 1 ] == true ) r ++ ;
		r += n ;
	}
	else {
		int &l = a [ now ] . l ;
		int &r = a [ now ] . r ;
		l = 1 ; r = n ;
		while ( vis [ l ] == false ) l ++ ;
		while ( vis [ r ] == false ) r -- ;
	}
	return ;
}


int main () {
	while ( scanf ( "%d" , & n ) == 1 and n ) {
		for ( int i = 1 ; i <= n ; i ++ ) 
			scanf ( "%lf%lf" , & p [ i ] . x , & p [ i ] . y ) ;
		p [ n + 1 ] = p [ 1 ] ;
		scanf ( "%d" , & m ) ;
		for ( int i = 1 ; i <= m ; i ++ ) {
			static vec x ;
			scanf ( "%lf %lf %d " , & x . x , & x . y , & a [ i ] . cost ) ;
			work ( x , i ) ;
		}
		static int ans ; ans = 0x3f3f3f3f ;
		for ( int i = 1 ; i <= n ; i ++ ) {
			memset ( f , 0x3f3f3f3f , sizeof ( f ) ) ;
			f [ i ] = 0 ;
			for ( int j = 0 ; j < n ;  j ++ ) {
				int now = i + j ;
				for ( int k = 1 ; k <= m ; k ++ ) {
					if ( a [ k ] . l > now or a [ k ] . r < now ) continue ;
					f [ min ( i + n , a [ k ] . r + 1 ) ] = min ( f [ min ( i + n , a [ k ] . r + 1 ) ] , f [ now ] + a [ k ] . cost ) ;
				}
			}
			ans = min ( ans , f [ i + n ] ) ;
		}
        if ( ans == 0x3f3f3f3f ) puts("Impossible.");
        else printf ( "%d\n" , ans ) ;
	}
	return 0 ; 
}

标签：const,point,int,double,ans,UVA10641,vec,Stadium,Barisal
From： https://www.cnblogs.com/dadidididi/p/17001014.html