题目大意:
要完成两种属性p,q的需求,给定n个双属性物品及其单位个物品中含有的属性,要求选择最少的物品来达成属性需求。(可以选择实数个物品)
题解:
实际上是一种属性混合问题
我们知道对于两种双属性物品,按照一定比例融合
可以配置出的物品的属性在二维平面上的分布一定是一条直线
而这条直线由最初的双属性物品所对应的点坐标所确定
扩展到三个物品,我们发现所有可配置的物品构成了一个三角形
扩展到n个物品,我们发现这n个点构成的凸包内的物品一定都可以配置
所以我们求出凸包来
然后我们从原点想我们的需求对应的点连一条射线
我们发现这条射线会交凸包于两点(?)
我们找出横纵坐标最大的点
此时我们知道:一定是使用配置出这个点的比例来乘以一个系数k来达到我们的需求
这个系数k就是我们的答案
完了么????
还没有
上面打了一个问号,其实是那里有一些问题。。。 。。。
我们发现这样做的话正确性不能保证,这条射线也不一定与凸包相交
... ...
所以我们再加两个点((max{a_i},0))和((0,max{b_i}))就行了
... ...
这两个点解决了所有的不妥以及不恰当。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 100010;
const double eps = 1e-9;
struct Point{
double x,y;
Point(const double a = .0,const double b = .0){x=a;y=b;}
void print(){
printf("Point (%lf,%lf)
",x,y);
}
};
typedef Point Vector;
Vector operator + (const Vector &a,const Vector &b){
return Vector(a.x+b.x,a.y+b.y);
}
Vector operator - (const Vector &a,const Vector &b){
return Vector(a.x-b.x,a.y-b.y);
}
double operator * (const Vector &a,const Vector &b){
return a.x*b.y - a.y*b.x;
}
Vector operator * (const Vector &a,const double &b){
return Vector(a.x*b,a.y*b);
}
inline int dcmp(const double &x){
if(x < eps && x > -eps) return 0;
return x > 0 ? 1 : -1;
}
inline bool cmp(const Point &a,const Point &b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int n,m;
Point p[maxn],ch[maxn];
void convex(){
sort(p+1,p+n+1,cmp);m = 0;
for(int i=1;i<=n;++i){
while(m > 1 && dcmp((ch[m] - ch[m-1])*(p[i] - ch[m])) <= 0) -- m;
ch[++m] = p[i];
}int k = m;
for(int i=n-1;i>=1;--i){
while(m > k && dcmp((ch[m] - ch[m-1])*(p[i] - ch[m])) <= 0) -- m;
ch[++m] = p[i];
}swap(n,m);swap(ch,p);
}
Point getPoint(Point p,Vector v,Point q,Vector w){
Vector u = p - q;
double t = (w*u)/(v*w);
return p+v*t;
}
inline double length(const Vector &x){
return sqrt(x.x*x.x+x.y*x.y);
}
#define nx(x) ((x) % n + 1)
bool vis[maxn];
int main(){
int xx,yy;read(n);read(xx);read(yy);
int maxx = 0,maxy = 0;
for(int i=1,x;i<=n;++i){
read(x);p[i].x = x;maxx = max(maxx,x);
read(x);p[i].y = x;maxy = max(maxy,x);
}p[++n] = Point(1.0*maxx,0.0);p[++n] = Point(0.0,1.0*maxy);
convex();Vector v(xx,yy);
Point pos[10];int cnt = 0;
for(int i=1;i<=n;++i){
if(dcmp(v*p[i]) == 0){
vis[i] = true;
pos[cnt++] = p[i];
}
}
for(int i=1;i<=n;++i){
if(vis[i] || vis[nx(i)]) continue;
Point a = p[i],b = p[nx(i)];
if(dcmp(a*v)*dcmp(b*v) <= 0){
pos[cnt++] = getPoint(Point(0,0),v,a,b-a);
}
}
if(cmp(pos[0],pos[1])) swap(pos[0],pos[1]);
double ans = length(v)/length(pos[0]);
printf("%.10lf
",ans);
getchar();getchar();
return 0;
}