计算几何/凸包/Floyd
Orz rausen大爷太强辣
计算几何题目果然不会做>_>
这个题……虽然他给了3个坐标，但实际上是个二维的计算几何题= =因为第三维坐标可以直接用前两维坐标表示出来。
考虑一下这些二维平面上的点的意义……
假如我们现在手里有一种原材料$(x_1,y_1)$，那么我们就只能搞出这一种合金= =
那么如果有两种原材料，我们配一配，就可以配出$(x_1,y_1)$到$(x_2,y_2)$这条线段上的所有合金= =
如果有三种，我们能配出的就是那个三角形区域的所有种类的合金……
以此类推……我们有n种原材料，我们能搞出的合金就是这n个点的凸包围出来的区域。
所以问题就变成了：从n个点中选出最少的p个点使得给定的m个点全部在这p个点的凸包内（主要意思是这样，当然还有一些边界情况，嗯就是共线、共点……）
这个是用floyd求最小环来做的……对于每对点(i,j)，如果m个点都在向量(i->j)的左边，则连边 i->j 权值为1，那么$ans=min\{dist[i][i]\}$
P.S.好像没有用到求凸包的算法……不过用了凸包的思想……
/**************************************************************
Problem: 1027
User: Tunix
Language: C++
Result: Accepted
Time:1172 ms
Memory:2288 kb
****************************************************************/ //BZOJ 1027
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-')r=-;
for(; isdigit(ch);ch=getchar()) v=v*+ch-'';
return r*v;
}
typedef double lf;
const lf eps=1e-;
const int N=,INF=1e9;
/*******************template********************/
int n,m,d[N][N];
struct Point{
double x,y;
Point(){}
Point(lf x,lf y):x(x),y(y){}
void read(){scanf("%lf%lf%*lf",&x,&y);}
inline bool operator != (const Point &p)const{
return fabs(x-p.x) > eps || fabs(y-p.y) > eps;
}
}a[N],b[N];
typedef Point Vector;
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
lf Cross(Point a,Point b){return a.x*b.y-a.y*b.x;} bool in_one_line(Point x,Point y){
if (x.x > y.x) swap(x,y);
F(i,,m) if (b[i].x < x.x || b[i].x > y.x) return ;
if (x.y > y.y) swap(x,y);
F(i,,m) if (b[i].y < x.y || b[i].y > y.y) return ;
return ;
}
int check(Point x,Point y){
int cnt1=,cnt2=; lf tmp;
F(i,,m){
tmp=Cross(y-x,b[i]-x);
if (tmp>eps) ++cnt1;
if (tmp<-eps) ++cnt2;
if (cnt1 && cnt2) return ;
}
if (!cnt1 && !cnt2 && in_one_line(x,y)){
puts("");
return -;
}
return cnt1 ? : cnt2 ? : ;
}
void Floyd(){
int ans=INF;
F(k,,n) F(i,,n) F(j,,n)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
F(i,,n) ans=min(ans,d[i][i]);
if (ans==INF || ans<=) puts("-1");
else printf("%d\n",ans);
}
void solve(){
F(i,,n) F(j,,n) d[i][j]=INF;
F(i,,n) F(j,i+,n){
int f=check(a[i],a[j]);
if (f==-) return;
if (f==) d[i][j]=;
else if (f==) d[j][i]=;
else if (f==) d[i][j]=d[j][i]=;
}
Floyd();
}
bool spj(){
F(i,,n) if (a[]!=a[i]) return ;
F(i,,m) if (a[]!=b[i]) return ;
puts("");
return ;
}
int main(){
n=getint(); m=getint();
F(i,,n) a[i].read();
F(i,,m) b[i].read();
if (spj()) return ;
solve();
return ;
}
1027: [JSOI2007]合金
Time Limit: 4 Sec Memory Limit: 162 MB
Submit: 2423 Solved: 635
[Submit][Status][Discuss]
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
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