注释掉第184行会只wa8,放出来会只wa2????哪位佬调一下啊
查看原帖
注释掉第184行会只wa8,放出来会只wa2????哪位佬调一下啊
819682
Exile_Code楼主2024/1/27 21:30
#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <functional>
#include <unordered_map>
#include <unordered_set>


#define ull             unsigned long long 
#define ll              long long
#define pii             pair<ll ,ll>
#define ft              first
#define sd              second
#define cy              cout<<"YES"<<endl
#define cn              cout<<"NO"<<endl
#define forn(i,n)       for(ll (i)=0;(i)<(n);(i)++)   
#define forne(i,n)      for(ll (i)=1;(i)<=(n);(i)++)
#define rforn(i,n)      for(ll (i)=(n-1);i>=0;i--)
#define rforne(i,n)     for(ll (i)=n;i>=1;i--)
#define vv              vector
#define inf32           INT32_MAX
#define inf64           INT64_MAX
#define LD              long double
#define PI              acos(-1)
#define debug(a,b)		cout<<a<<b
#define eps				1e-20
const int N = 4e5 + 100;
const int mod = 998244353;
ll T;



//点类
struct Point {
	LD x, y;
	Point(LD x, LD y) { this->x = x;	this->y = y; }
	Point() {}
#define line Point 
	//点的加减乘运算
	Point operator+(Point b) { return Point(this->x + b.x, this->y + b.y); }
	Point operator-(Point b) { return Point(this->x - b.x, this->y - b.y); }
	Point operator*(LD t) { return Point(this->x * t, this->y * t); }
	LD operator*(Point b) { return this->x * b.x + this->y * b.y; }
	bool operator==(Point b) { return this->x == b.x && this->y == b.y; }
};
class Geomtry_tool {
public:
	//求长度
	static LD len(line a) { return sqrt(a.x * a.x + a.y * a.y); }
	//求两点距离
	LD dis(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
	//两个向量求角度,使用的是余弦定理求arccos
	static LD angle(line a, line b) { return acos(a * b / len(a) / len(b)); }
	//两个向量求叉积
	static LD cross(line a, line b) { return a.x * b.y - a.y * b.x; }
	//epslion,判断是否等于0
	static int sgn(LD x) {  return fabs(x) <= eps ? 0 : x > 0 ? 1 : -1; }
	//防止负0的发生
	static void zero(Point& a) { if (fabs(a.x) <= eps)a.x = 0; if (fabs(a.y) <= eps)a.y = 0; }
	//可以用来判断c在b的左侧还是右侧
	//大于0,c在ab左侧;小于0,c在ab右侧;等于0,三点共线
	static LD cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
	//三点点积ab*ac
	static LD dot(Point a, Point b, Point c) { return (b - a) * (c - a); }
	//判断直线与线段的交点情况,在同侧则无交点;
	//如果是判断线段与线段有无交点,则需要分别设ab,cd为直线,进行两次判断
	static bool l_S_inter(Point a, Point b, Point c, Point d) {
		return sgn(cross(a, b, c) * cross(a, b, d)) <= 0;//直线与线段
	}
	//线段与线段
	static bool S_S_inter(Point a, Point b, Point c, Point d) {
		return l_S_inter(a, b, c, d) && l_S_inter(c, d, a, b);
	}
	//求两直线的交点
	static Point getNode(Point a, line u, Point b, line v) {
		LD t = cross((a - b), v) / cross(v, u);//求面积之比
		return a + u * t;
	}
	static Point rotate(Point a, LD b) { //将某点绕原点逆时针旋转b角度
		return { a.x * cos(b) - a.y * sin(b), a.x * sin(b) + a.y * cos(b) };
	}
	static LD get_S(vv<Point>& p) {
		int k = p.size() - 1; LD res = 0;
		for (int i = 2; i < k; i++)
			res += cross((p[i] - p[1]), (p[i + 1] - p[1]));
		return res / 2.0;
	}
};

//凸包
class Andrew {
	Geomtry_tool fn;
public:
	int top = 0;
	struct cmp {
		bool operator()(const Point& a, const Point& b) {
			return a.x == b.x ? a.y < b.y : a.x < b.x;
		}
	};
	LD Andrew_lenth(vv<Point>& p, vv<Point>& s) {
		int n = p.size() - 1;
		sort(p.begin() + 1, p.end(), cmp());
		s = vv<Point>(p.size() + 2);//p条线,区间[1,n+1]多加上封口的一条
		//最左下和最右上的两个点一定是在凸包上的
		forne(i, n) {//下凸包
			while (top > 1 && fn.sgn(fn.cross(s[top - 1], s[top], p[i]) <= 0))
				top--;
			s[++top] = p[i];
		}
		int t = top;
		for (int i = n - 1; i >= 1; i--) {//上凸包
			while (top > t && fn.sgn(fn.cross(s[top - 1], s[top], p[i])) <= 0)
				top--;
			s[++top] = p[i];
		}
		LD res = 0;
		for (int i = 1; i < top; i++)
			res += fn.dis(s[i], s[i + 1]);
		return res;
	}
	//旋转卡壳,用叉积可以找离一条线垂直最高或最低,用点积可以找离一条线水平最左或最右的点(点积的几何意义是b在a的投影长度)
	LD rotating_calipers(vv<Point>& s) {
		int n = top - 1;//缩掉最后封口的点
		LD res = 0;
		for (int i = 1, j = 2; i <= n; i++) {
			while (fn.cross(s[i], s[i + 1], s[j])
				< fn.cross(s[i], s[i + 1], s[j + 1]))//因为缩了一个点,所以j+1不会越界
				j = j % n + 1;
			res = max(res, max(fn.dis(s[i], s[j])
				, fn.dis(s[i + 1], s[j])));
		}
		return res;
	}
};

struct Line { Point s, e;ll id; };

//半平面交
class Half_plane {
private:
	Geomtry_tool fn;
public:
	int h = 1, t = 1;
	static LD angle(Line a) {//求极角
		return atan2(a.e.y - a.s.y, a.e.x - a.s.x);
	}
	struct cmp {
		Geomtry_tool fn;
		bool operator()(Line a, Line b) {//极角+左侧优先排序
			LD A = angle(a), B = angle(b); 
			return fabs(A - B) > eps ? A < B :fn.sgn(fn.cross((a.e - a.s), (b.e - a.s))) < 0;
		}
	};
	Point cross(Line a, Line b) {//求ab两线交点
		return fn.getNode(a.e, a.s - a.e, b.e, b.s - b.e);
	}
	bool right_nd(Line a, Line b, Line c) {//判断bc交点是否在a右侧
		Point p = cross(b, c);
		return fn.sgn(fn.cross((a.e - a.s), (p - a.s))) < 0;
	}
	void half_plane(vv<Line>& a, vv<Line>& q) {//[1,n+1],[1,n+1]
		q = vv<Line>(a.size() + 1);
		q[1] = a[1];
		sort(a.begin() + 1, a.end(), cmp());
		h = 1, t = 1; q[1] = a[1];
		int n = a.size() - 1;
		for (int i = 2; i <= n; i++) {
			//必须先弹出尾再弹出头
			//if (angle(a[i])-angle(a[i-1])<=1e-15)continue;
			while (h < t && right_nd(a[i], q[t], q[t - 1]))t--;
			while (h < t && right_nd(a[i], q[h], q[h + 1]))h++;
			q[++t] = a[i];
		}
		//while (h < t && right_nd(q[h], q[t], q[t - 1]))t--;

	}
};

Geomtry_tool fn;
void solve() {

	int n; cin >> n;

	vv<Line>p(n + 1);
	vv<LD>k(n + 1);
	vv<LD>v(n + 1);
	forne(i, n)
		cin >> k[i];

	forne(i, n)
		cin >> v[i];

	forne(i, n) {
		p[i] = { {0,k[i]},{1,k[i] + v[i]},i };
	}
	p.push_back({{ 0.0,0.0 }, { 0.0,-1.0 }, 0});
	Half_plane hp;
	vv<Line>rs;
	hp.half_plane(p,rs);
	auto cmp2 = [](Line a, Line b)->bool {
		return a.id < b.id;
	};

	sort(rs.begin() + 1, rs.begin() + hp.t + 1, cmp2);

	cout << hp.t - 2 + 1 << endl;
	for (int i = 2; i <= hp.t; i++) {
		cout << rs[i].id << ' ';
	}

}
int main() {

	//std::ios::sync_with_stdio(false);
	T = 1;
	//cin >> T;

	while (T--)
		solve();

}
2024/1/27 21:30
加载中...