bzoj1027: [JSOI2007]合金

每种材料可以用前两个表示，设为X，Y，分别作为横纵坐标，那么两个点的连线上的点都可以被这两个点表示，几个点围城的凸包可以表示凸包内的所有点，那么问题就转化为求最少的点，使他们围城的凸包能够包含所有的点，答案用最小环求解

 

//-----------------------------------发现原来的代码有点bug，虽然可以AC，但最小环是错的，以更正

const int N = 510;
const DB Eps = 1e-9;
typedef pair<DB, DB> DD;
int n, m;
DD Material[N], Product[N];
int Dist[N][N], Graph[N][N], Ans;

inline void Input() {
	scanf("%d%d", &n, &m);
	DB C;
	For(i, 1, n) scanf("%lf%lf%lf", &Material[i].ft, &Material[i].sd, &C);
	For(i, 1, m) scanf("%lf%lf%lf", &Product[i].ft, &Product[i].sd, &C);
}

inline void Exit(int Ret) {
	printf("%d\n", Ret);
	exit(0);
}

inline int Judge(DB X) {
	if(X > -Eps && X < Eps) return 0;
	if(X > Eps) return 1;
	return -1;
}

inline bool Single(int X) {
	For(i, 1, m)
		if(Judge(Material[X].ft-Product[i].ft) != 0 || 
		   Judge(Material[X].sd-Product[i].sd) != 0) return 0;
	return 1;
}

inline bool Couple(int X, int Y) {
	DB X1 = Material[Y].ft-Material[X].ft, Y1 = Material[Y].sd-Material[X].sd;
	For(i, 1, m) {
		DB X2 = Product[i].ft-Material[X].ft, Y2 = Product[i].sd-Material[X].sd;
		if(Judge(Y2*X1-X2*Y1) != 0) return 0;
		if(Judge(X1*X2) < 0 || Judge(Y1*Y2) < 0) return 0;
		if(Judge(abs(X1)-abs(X2)) < 0 && Judge(abs(Y1)-abs(Y2)) < 0) return 0;
	}
	return 1;
}

inline bool Check(int X, int Y) {
	if(X == Y) return 0;
	DB X1 = Material[Y].ft-Material[X].ft, Y1 = Material[Y].sd-Material[X].sd;
	For(i, 1, m) {
		DB X2 = Product[i].ft-Material[X].ft, Y2 = Product[i].sd-Material[X].sd;
		if(Judge(X1*Y2-X2*Y1) < 0) return 0; 
	}
	return 1;
}

inline void Solve() {
	For(i, 1, n)
		if(Single(i)) Exit(1);
	For(i, 1, n)
		For(j, i+1, n)
			if(Couple(i, j)) Exit(2);
	
	For(i, 1, n)
		For(j, 1, n)
			Dist[i][j] = Graph[i][j] = Check(i, j) ? 1 : n+1;
	
	Ans = n+1;
	For(k, 1, n) {
		For(i, 1, k-1)
			For(j, 1, k-1) gmin(Ans, Dist[i][j]+Graph[k][i]+Graph[j][k]);
		For(i, 1, n)
			For(j, 1, n) gmin(Dist[i][j], Dist[i][k]+Dist[k][j]);
	}
	
	printf("%d\n", Ans > n ? -1 : Ans);
}

int main() {
	SetIO("1959");
	Input();
	Solve();
	return 0;
}