题目大意
给出一些由三种金属组成的原料，用这些原料去组成用户需要的一定比例的金属。问要达成用户的需求，最少需要多少种原料。
思路
这是隐藏的很好的一道计算几何题。因为两个坐标就可以表示一种金属了。 然后我们把这些点放在平面上，发现两种不同的金属能够组成的范围是这两个点所构成的有向线段的左侧，，这样我们求出所有满足要求的这样的有向线段，之后跑Floyd来求出最小环，就是我们需要的答案。
CODE;#define INRANGE(x, y, c) ((c <= x && c >= y) || (c <= y && c >= x))struct Point{double x, y;Point(double _, double __):x(_), y(__) {}Point() {}Point operator -(const Point &a)const {return Point(x – a.x, y – a.y);}void Read() {scanf(“%lf%lf%*lf”, &x, &y);}}src[MAX], ask[MAX];inline double Cross(const Point &p1, const Point &p2){return p1.x * p2.y – p1.y * p2.x;}struct Line{Point p, v, _p;Line(const Point &_, const Point &__):p(_), v(__ – _), _p(__) {}Line() {}bool OnLine(const Point &a)const {if(fabs(Cross(p – a, v)) > EPS)return false;if(p.x == _p.x)return INRANGE(p.y, _p.y, a.y);return INRANGE(p.x, _p.x, a.x);}bool OnLeft(const Point &a)const {return Cross(p – a, v) > 0 || OnLine(a);}};int cnt, asks;int map[MAX][MAX];inline bool Same(int p){for(int i = 1; i <= asks; ++i)if(ask[i].x != src[p].x || ask[i].y != src[p].y)return false;return true;}bool SpecialJudge(){if(!asks) {puts(“0”);return true;}for(int i = 1; i <= cnt; ++i)if(Same(i)) {puts(“1”);return true;}return false;}int Floyd(){for(int k = 1; k <= cnt; ++k)for(int i = 1; i <= cnt; ++i)for(int j = 1; j <= cnt; ++j)map[i][j] = min(map[i][j], map[i][k] + map[k][j]);int ans = INF;for(int i = 1; i <= cnt; ++i)ans = min(ans, map[i][i]);return ans == INF ? -1:ans;}int main(){cin >> cnt >> asks;for(int i = 1; i <= cnt; ++i)src[i].Read();for(int i = 1; i <= asks; ++i)ask[i].Read();if(SpecialJudge())return 0;memset(map, 0x3f, sizeof(map));for(int i = 1; i <= cnt; ++i)for(int j = 1; j <= cnt; ++j) {if(i == j) continue;bool flag = true;Line t(src[i], src[j]);for(int k = 1; k <= asks; ++k)if(!t.OnLeft(ask[k])) {flag = false;break;}map[i][j] = flag ? 1:INF;}cout << Floyd() << endl;return 0;}
有多少和我一样，坐在不足平米的空间里，
