90求条 wa#8
查看原帖
90求条 wa#8
533102
monodev楼主2024/9/9 21:37
#include <iostream>
using namespace std;

const int MAXN = 5 + 1, inf = 1 << 30;
int n, s;

struct Segment {
	int l, r, end;
	double k, b;
} seg[MAXN + MAXN + MAXN / 2];

double getValue(int x, int i) {
	return seg[i].k * x + seg[i].b;
}

int dropAns;
bool drop(int& height) {
	bool returnValue = false;
	double highest = -inf;
	for(int i = 0; i < n; ++ i) {
		if(seg[i].l < s && seg[i].r > s) {
			double thisHeight = seg[i].k * s + seg[i].b;
			if(thisHeight > highest && thisHeight <= height) {
				dropAns = i;
				highest = thisHeight;
				returnValue = true;
			}
		}
	}
	s = seg[dropAns].end;
	height = seg[dropAns].k * s + seg[dropAns].b;
	return returnValue;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> s;
	for(int i = 0; i < n; ++ i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1 > x2) {
			swap(x1, x2);
			swap(y1, y2);
		}
		seg[i].l = x1;
		seg[i].r = x2;
		seg[i].end = y1 < y2 ? x1 : x2;
		seg[i].k = (double)(y1 - y2) / (x1 - x2);
		seg[i].b = y1 - seg[i].k * x1;
	}
	
	int nowHeight = inf;
	while(drop(nowHeight));
	cout << s << endl;
	
	return 0;
}
2024/9/9 21:37
加载中...