2 条题解

  • 0
    @ 2025-6-16 10:57:39

    题意分析

    本题是一个铁人三项比赛的问题，核心是判断是否存在合理的各段赛程长度，使得某一选手成为唯一的冠军。具体要求如下：

    • 铁人三项由游泳、骑自行车、跑步三个连续项目组成
    • 每个选手在三个项目上有不同的速度
    • 裁判可以任意选择各段赛程的长度（不能为0）
    • 需要判断是否存在一组赛程长度，使得指定选手的总用时严格小于其他所有选手的总用时

    关键转化

    设三个项目的长度分别为 (a, b, c)（均大于0），第 (i) 个选手的总用时为： [ t_i = \frac{a}{v_i} + \frac{b}{u_i} + \frac{c}{w_i} ] 要让第 (x) 个选手获胜，需满足对所有 (i \neq x)，有： [ \frac{a}{v_x} + \frac{b}{u_x} + \frac{c}{w_x} < \frac{a}{v_i} + \frac{b}{u_i} + \frac{c}{w_i} ]

    解题思路

    不等式变形

    将上述不等式移项整理，得到： [ a\left(\frac{1}{v_i} - \frac{1}{v_x}\right) + b\left(\frac{1}{u_i} - \frac{1}{u_x}\right) + c\left(\frac{1}{w_i} - \frac{1}{w_x}\right) > 0 ] 令 (x = \frac{a}{c}, y = \frac{b}{c})（因 (c > 0)，变量替换不改变不等式方向），则不等式转化为： [ \left(\frac{1}{v_i} - \frac{1}{v_x}\right)x + \left(\frac{1}{u_i} - \frac{1}{u_x}\right)y + \left(\frac{1}{w_i} - \frac{1}{w_x}\right) > 0 ]

    半平面交模型

    • 每个不等式对应二维平面上的一个半平面（直线一侧的区域）
    • 我们需要判断这些半平面的交集是否存在非空区域
    • 若存在，则说明存在合法的 (x, y)，即存在合法的 (a, b, c)

    边界处理

    • 初始半平面为 (x \geq 0, y \geq 0)（因 (a, b, c > 0)，故 (x, y > 0)）
    • 用四个边界点 ((0,0), (\infty,0), (\infty,\infty), (0,\infty)) 构造初始凸多边形
    • 对每个选手 (i \neq x)，生成对应的半平面并切割凸多边形
    • 若最终凸多边形的边数 ≥ 3，说明存在可行解

    代码实现与解析

    #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps = 1e-6;
const double pi = acos(-1.0);
const double inf = 1.0 * 0x3f3f3f3f;
const int MaxN = 555;

int n, M;
double u[MaxN], v[MaxN], w[MaxN];  // 存储各选手三个项目的速度

// 点结构定义
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};
typedef Point Vector;

// 直线结构定义
struct Line {
    Point s, e;
    Line() {}
    Line(Point a, Point b) { s = a, e = b; }
};

// 三参数直线方程结构
struct NODE {
    double a, b, c;
};

// 浮点数比较函数
int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

// 向量运算重载
Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
Vector operator - (Vector A, Vector B) { return Vector(A.x-B.x, A.y-B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
bool operator == (const Point &a, const Point &b) {
    return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}

// 向量点积与叉积
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }

// 计算两点距离（平方）
double dis(Point A, Point B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

// 初始化初始凸多边形（第一象限边界）
void init() {
    p[1].x = 0.0, p[1].y = 0.0;
    p[2].x = inf, p[2].y = 0.0;
    p[3].x = inf, p[3].y = inf;
    p[4].x = 0, p[4].y = inf;
    p[5] = p[1], p[0] = p[4];  // 环数组处理
    M = 4;  // 初始边数为4
}

// 计算两直线交点
Point Ist_LP(Line a, double a2, double b2, double c2) {
    double a1 = a.e.y - a.s.y, b1 = a.s.x - a.e.x, c1 = a.e.x * a.s.y - a.s.x * a.e.y;
    return Point((c1*b2 - c2*b1)/(a2*b1 - a1*b2), (a2*c1 - a1*c2)/(a1*b2 - a2*b1));
}

// 获取直线的一般式方程
NODE get_abc(Line X) {
    NODE cur;
    Point S = X.s, E = X.e;
    cur.a = E.y - S.y;
    cur.b = S.x - E.x;
    cur.c = S.y*E.x - S.x*E.y;
    return cur;
}

// 半平面切割操作
void cut(double a, double b, double c) {
    int cnt = 0;
    for (int i = 1; i <= M; i++) {
        // 点在半平面内（a*x + b*y + c <= 0）
        if (dcmp(a * p[i].x + b * p[i].y + c) <= 0) {
            C[++cnt] = p[i];
        } else {
            // 与前后边求交点
            if (dcmp(a * p[i-1].x + b * p[i-1].y + c) < 0) {
                C[++cnt] = Ist_LP(Line{p[i-1], p[i]}, a, b, c);
            }
            if (dcmp(a * p[i+1].x + b * p[i+1].y + c) < 0) {
                C[++cnt] = Ist_LP(Line{p[i], p[i+1]}, a, b, c);
            }
        }
    }
    // 更新凸多边形
    for (int i = 1; i <= cnt; i++) p[i] = C[i];
    p[0] = C[cnt];
    p[cnt+1] = C[1];
    M = cnt;
}

// 判断选手x是否可能获胜
bool HalfPlane(int x) {
    M = 4;  // 初始化为4个边界点
    init();
    
    // 检查是否有选手全面优于x
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        if (u[i] >= u[x] && v[i] >= v[x] && w[i] >= w[x]) {
            return false;  // 存在选手全面更快，x无法获胜
        }
    }
    
    // 对每个其他选手生成半平面并切割
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        double a = (u[i] - u[x]) / (u[x] * u[i]);
        double b = (v[i] - v[x]) / (v[x] * v[i]);
        double c = (w[i] - w[x]) / (w[x] * w[i]);
        cut(a, b, c);
        if (M <= 2) return false;  // 无可行区域
    }
    return M >= 3;  // 存在可行区域
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf%lf", &u[i], &v[i], &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (HalfPlane(i)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

    算法关键点解析

    1. 半平面交模型：

      • 将时间比较转化为线性不等式
      • 每个不等式对应一个半平面，通过切割操作维护可行区域

    2. 初始区域设置：

      • 初始区域为第一象限（(x \geq 0, y \geq 0)），对应 (a, b, c > 0)

    3. 切割操作：

      • 对每个半平面，保留在平面左侧的点
      • 计算边界交点，更新凸多边形

    4. 提前终止优化：

      • 若存在选手全面优于当前选手x，直接判定x无法获胜
      • 若切割后凸多边形边数≤2，说明无可行区域

    复杂度分析

    • 时间复杂度：(O(N^3))，其中N为选手数量

      • 对每个选手执行一次半平面交，每次半平面交需要处理N-1个半平面
      • 每个半平面切割的时间复杂度为 (O(M))，M为当前凸多边形边数（最多4）

    • 空间复杂度：(O(N))，存储选手速度和凸多边形顶点

    样例分析

    以输入数据为例，当判断第1个选手时：

    1. 初始化凸多边形为第一象限边界
    2. 对其他8个选手生成半平面并切割
    3. 若最终凸多边形边数≥3，说明存在可行的赛程长度，输出"Yes"
    4. 否则输出"No"

    该算法通过半平面交高效判断了是否存在让特定选手获胜的赛程组合，能够正确处理所有合法输入。

    • 0
      @ 2025-5-27 20:24:05

      题意 给你n个人铁人三项的速度（n<=100），每项比赛长度可调节，问你对于每个人来说，调节比赛长度这个人有没有获胜（比剩下人都快）的可能。

      思路 三项速度设为ui,vi,wi 长度a b c

      t = a / ux + b / vx + c / wx;

      获胜需满足对于所有i: (1/ux - 1/ui)*a + (1/vx - 1/vi)*b + (1/wx - 1/wi)*c < 0 已知c!=0,那么可将c除过去

      即 (1/ux - 1/ui)*a/c + (1/vx - 1/vi)*b/c + (1/wx - 1/wi) < 0,那么就转换为求n-1条ax+by+c<0的不等式是否有可行性区域。

      这里init四个边界点：(0,0) (inf,0) (inf,inf) (0,inf) 因为可行的答案比赛长度一定正数，此时半平面交n^2求是否有凸核M >= 3就ok了

      #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double inf = 1.0 * 0x3f3f3f3f;
const int MaxN = 555;
 
int n,M;
double u[MaxN],v[MaxN],w[MaxN];
struct Point{
	double x,y;
	Point(double x = 0,double y = 0) : x(x),y(y) {}
}a[MaxN],p[MaxN],C[MaxN];
typedef Point Vector;
 
struct Line{
	Point s,e;
	Line() {}
	Line(Point a,Point b){ s = a,e = b;}
}L[MaxN];
 
struct NODE{
	double a,b,c;
};
 
int dcmp(double x){//equal ?= 0
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1:1;
}
 
//运算符重载
Vector operator + (Vector A, Vector B){ return Vector(A.x+B.x, A.y+B.y); }
Vector operator - (Vector A, Vector B){ return Vector(A.x-B.x, A.y-B.y); }
Vector operator * (Vector A, double p){ return Vector(A.x*p, A.y*p); }
bool operator == (const Point &a, const Point &b){
	return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}
 
double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }
double Cross(Vector A, Vector B){ return A.x*B.y - A.y*B.x; }
 
double dis(Point A,Point B){
	return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
 
void init(){
	p[1].x = 0.0,p[1].y = 0.0;
	p[2].x = inf,p[2].y = 0.0;
	p[3].x = inf,p[3].y = inf;
	p[4].x = 0,p[4].y = inf;
	p[5] = p[1],p[0] = p[4];
}
 
Point Ist_LP(Line a,double a2,double b2,double c2){//给两直线求交点
	double a1 = a.e.y - a.s.y,b1 = a.s.x - a.e.x,c1 = a.e.x * a.s.y - a.s.x * a.e.y;
//	double a2 = b.s.y - b.e.y,b2 = b.e.x - b.s.x,c2 = b.s.x * b.e.y - b.e.x * b.s.y;
	return Point((c1*b2 - c2*b1)/(a2*b1 - a1*b2), (a2*c1 - a1*c2)/(a1*b2 - a2*b1));
}
 
NODE get_abc(Line X){
	NODE cur;
	Point S = X.s,E = X.e;
	cur.a = E.y - S.y;//后y - 前y
	cur.b = S.x - E.x;//前x - 后x
	cur.c = S.y*E.x - S.x*E.y;//前y*后x - 前x*后y
	return cur;
}
 
void cut(double a,double b,double c){
	int cnt = 0;//这把cut完的凸核还剩几个点
	for(int i = 1;i <= M; i++){
		if(a * p[i].x + b * p[i].y + c <= 0){
			C[++cnt] = p[i];//这次cur产生的点数组
		}//<=0:p[i]点在平移后的直线的左边 √
		else{
			//当前点与前后临接点 与平移后的直线相交
			//这里不需要= 都=了还求个锤子交点那不是直接放进去了
			if(a * p[i - 1].x + b * p[i - 1].y + c < 0){
				C[++cnt] = Ist_LP((Line){p[i-1],p[i]},a,b,c);
			}	
			if(a * p[i + 1].x + b * p[i + 1].y + c < 0){
				C[++cnt] = Ist_LP((Line){p[i],p[i+1]},a,b,c);//那得给整个点吧
			}
		}
	}
	for(int i = 1;i <= cnt; i++) p[i] = C[i];
	p[0] = C[cnt];
	p[cnt + 1] = C[1];//p[]存的是上一次cut完剩下的点 环数组
	M = cnt;
}
 
bool HalfPlane(int x){//半平面交
	M = 4;//4个边界
	for(int i = 1;i <= n; i++){
		if(i == x) continue;
		if(u[i] >= u[x] && v[i] >= v[x] && w[i] >= w[x]) return 0;
	}//三项都比你快 你还和人家比个锤子 别丢人了GG
	for(int i = 1;i <= n;i++){
		if(i == x) continue;//判断剩下n-1个表达式是否有可行性区域
		double a = (u[i] - u[x]) / (u[x] * u[i]);
		double b = (v[i] - v[x]) / (v[x] * v[i]);
		double c = (w[i] - w[x]) / (w[x] * w[i]);
		cut(a,b,c);
		if(M <= 2) return 0;
	}
	return M >= 3;
}
 
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n; i++){
		scanf("%lf%lf%lf",&u[i],&v[i],&w[i]);
	}
	for(int i = 1;i <= n; i++){
		init();
		if(HalfPlane(i)) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
      • 1

      Triathlon

      信息

      ID
      756
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      2
      已通过
      2
      上传者
      1. 评测队列
      2. 服务状态
      3. 兼容模式
      4. 主题
      2. 黔ICP备2023002402号-2
      3. Worker 0, 48ms
      4. Powered by Hydro v4.19.1 Community, Modified by 33DAI