[USACO Mar10]星牛争霸StarCowraft解题报告

题目


分析

首先可以发现,我们能够把三种单位的战斗力同时乘以一个数而不改变结果。因此,不妨设第三种单位的战斗力S3=1.出于方便,不妨记x=S1,y=S2

对于一场比赛,我们能够写出一个类似这样的式子:

j1x+j2y+j3<=b1x+b2y+b3(当然也有可能是>=)

整理后得到一个类似这样的式子:

ax+by<=c

后面的朋友们,大声告诉我这叫什么?

没错,半平面!

所以做法就很简单了:对所有测试局的半平面求交,其交集(或曰‘核’)是一个凸多边形。将其所有顶点求出。在试图判断一次新的战斗时,显然该场战斗对应于一条直线,如果凸多边形的所有顶点均在直线一侧,那么该战斗的结果是确定的,否则不定。

注意,那个“单位之差不超过100”倍的条件也是要写出来的。

代码

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double eps=1e-10,pi=acos(-1.0),INF=1e10;
const int SIZE=2010;
class Point{
public:
	double x,y;
};
void print(const Point &p){
	cout<<"("< &Q){
	//要求此时已经计算出所有半平面的极角,存于h[1..n]
	//Q中返回约束了核的那些半平面
	sort(h+1,h+1+n,cmp);
	int tot=0;
	for(int i=1;i<=n;i++){//多个约束取最紧者
		if(tot==0||fabs(h[tot].pa-h[i].pa)>eps) h[++tot]=h[i];
		else if(h[i].c=2&&!inside(inter(Q.back(),Q[Q.size()-2]),h[i])) Q.pop_back();
		while(Q.size()>=2&&!inside(inter(Q[0],Q[1]),h[i])) Q.pop_front();
		Q.push_back(h[i]);
	}
	while(Q.size()>=2&&!inside(inter(Q.back(),Q[Q.size()-2]),Q[0])) Q.pop_back();
}
int check(const vector &v,const H_Plane &h){
	double mx=-INF,mn=INF;
	for(int i=0;ih.c+eps) return -1;//不符合h的判断
	else return 0;
}
int N,M;
H_Plane test_battle[SIZE];
deque core;
vector core_points;
void work(void){
	HPL_intersection(test_battle,N,core);
	for(int i=0;i

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注