Description
某公司加工一種由鐵、鋁、錫組成的合金。他們的工作很簡單。首先進口一些鐵鋁錫合金原材料,不同種類的
原材料中鐵鋁錫的比重不同。然後,将每種原材料取出一定量,經過融解、混合,得到新的合金。新的合金的鐵鋁
錫比重為使用者所需要的比重。 現在,使用者給出了n種他們需要的合金,以及每種合金中鐵鋁錫的比重。公司希望能
夠訂購最少種類的原材料,并且使用這些原材料可以加工出使用者需要的所有種類的合金。
Input
第一行兩個整數m和n(m, n ≤ 500),分别表示原材料種數和使用者需要的合金種數。第2到m + 1行,每行三
個實數a, b, c(a, b, c ≥ 0 且 a + b + c = 1),分别表示鐵鋁錫在一種原材料中所占的比重。第m + 2到m +
n + 1行,每行三個實數a, b, c(a, b, c ≥ 0 且 a + b + c = 1),分别表示鐵鋁錫在一種使用者需要的合金中
所占的比重。
Output
一個整數,表示最少需要的原材料種數。若無解,則輸出–1。
Sample Input
10 10
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0
Sample Output
5
解題方法:
第三維可以由前兩維确定,是以可以無視
兩種原料能配成的産品一定在兩點間線段
轉化成在m個點裡找最少點,圍成的多邊形包括了n個目标點
floyd求最小環。。。
具體就是如果目标點線上段a,b的一側則dis[a][b]=1
否則dis[a][b]=inf
答案是min{dis[i][i]}
特判下所有點重合/共線
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-10
const int inf = 1e8;
void getmin(int &x, int y){
if(y < x) x = y;
}
struct Point{
double x, y;
Point(){}
Point(double x, double y) : x(x), y(y) {}
}a[505], b[505];
int dis[505][505];
double cross(Point u, Point v){
return u.x*v.y - u.y*v.x;
}
Point operator -(Point u, Point v){
return Point(u.x - v.x, u.y - v.y);
}
int n, m;
bool isinline(Point u, Point v){
if(u.x > v.x) swap(u, v);
for(int i = 1; i <= m; i++){
if(b[i].x < u.x || b[i].x > v.x) return false;
}
if(u.y > v.y) swap(u, v);
for(int i = 1; i <= m; i++){
if(b[i].y < u.y || b[i].y > v.y) return false;
}
return 1;
}
int leftorright(Point u, Point v){
int c1 = 0, c2 = 0;
for(int i = 1; i <= m; i++){
double t = cross(v - u, b[i] - u);
if(t > eps) c1++;
if(t < -eps) c2++;
if(c1*c2) return 0;
}
if(!c1 && !c2 && isinline(u, v)){
puts("2");
return -1;
}
if(c1) return 1;
if(c2) return 2;
return 3;
}
void floyd(){
int ans = inf;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(dis[j][i] < inf){
for(int k = 1; k <= n; k++){
if(dis[j][k] > dis[j][i] + dis[i][k]){
dis[j][k] = dis[j][i] + dis[i][k];
}
}
}
}
}
for(int i = 1; i <= n; i++){
ans = min(ans, dis[i][i]);
}
if(ans == inf || ans <= 2)
{
puts("-1");
}
else{
printf("%d\n", ans);
}
}
void getmaze(){
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
int x = leftorright(a[i], a[j]);
if(x == -1) return;
else if(x == 1) dis[i][j] = 1;
else if(x == 2) dis[j][i] = 1;
else if(x == 3) dis[i][j] = dis[j][i] = 1;
}
}
floyd(); //必須寫在這裡,不能寫在外面,因為傳回-1代表不滿足了
}
bool pre_judge(){ //判斷是否全部重合
for(int i = 1; i <= n; i++){
if(fabs(a[i].x - a[1].x) > eps || fabs(a[i].y - a[1].y) > eps) return 0;
}
for(int i = 1; i <= m; i++){
if(fabs(b[i].x - a[1].x) > eps || fabs(b[i].y - a[1].y) > eps) return 0;
}
puts("1");
return 1;
}
int main(){
memset(dis, 0x3f, sizeof(dis));
double tmp;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &tmp);
for(int i = 1; i <= m; i++) scanf("%lf%lf%lf", &b[i].x, &b[i].y, &tmp);
if(pre_judge()){
return 0;
}
getmaze();
return 0;
}