QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249503#7569. LinesUSP_USP_USPCompile Error//C++209.9kb2023-11-12 11:06:192023-11-12 11:06:20

Judging History

你现在查看的是最新测评结果

  • [2023-11-12 11:06:20]
  • 评测
  • [2023-11-12 11:06:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define int int64_t
#define pb push_back

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }


constexpr double EPS = 1e-10;

bool zero(double x) {
	return abs(x) <= EPS;
}

// CORNER: point = (0, 0)
struct point {
	double x, y;
	
	point(): x(0), y(0) {}
	point(double _x, double _y): x(_x), y(_y) {}
	
	point operator+(point rhs) { return point(x+rhs.x, y+rhs.y); }
	point operator-(point rhs) { return point(x-rhs.x, y-rhs.y); }
	point operator*(double k) { return point(x*k, y*k); }
	point operator/(double k) { return point(x/k, y/k); }
	double operator*(point rhs) { return x*rhs.x + y*rhs.y; }
	double operator^(point rhs) { return x*rhs.y - y*rhs.x; }

	point rotated(point polar) { return point(*this^polar,*this*polar); }
	point rotated(double ang) { return (*this).rotated(point(sin(ang),cos(ang))); }
	double norm2() { return *this * *this; }
	double norm() { return sqrt(norm2()); }

	// dont know, taken from el-vasito
	double angle(point p) { return acos(*this * p / ( norm() * p.norm() )); }

	bool operator<(const point& rhs) const {
		return x < rhs.x - EPS || (zero(x-rhs.x) && y < rhs.y - EPS);
	}

	bool operator==(const point& rhs) const {
		return zero(x-rhs.x) && zero(y-rhs.y);
	}
};

const point ccw90(1, 0), cw90(-1, 0);

// angular comparison in [0, 2pi)
// smallest is (1, 0)
// CORNER: a || b == (0, 0)
bool ang_cmp(point a, point b) {
	auto quad = [](point p) -> bool {
		// 0 if ang in [0, pi), 1 if in [pi, 2pi)
		return p.y < 0 || (p.y == 0 && p.x < 0);
	};
	using tup = tuple<bool, double>;
	return tup{quad(a), 0} < tup{quad(b), a^b};
}

double dist2(point p, point q) { // squared distance
    return (p - q)*(p - q);
}

double dist(point p, point q) {
    return sqrt(dist2(p, q));
}

double area2(point a, point b, point c) { // two times signed area of triangle abc
	return (b - a) ^ (c - a);
}

// CORNER: BE CAREFUL WITH PRECISION WITH THESE FUNCTIONS, 
// 	IF NEEDED NORMALIZE (b-a) AND (c-a)
bool left(point a, point b, point c) {
	return area2(a, b, c) > EPS; // counterclockwise
}

bool right(point a, point b, point c) {
	return area2(a, b, c) < -EPS; // clockwise
}

bool collinear(point a, point b, point c) {
	return zero(area2(a,b,c));
}

// CORNER: a || b == (0, 0)
int parallel(point a, point b) {
	a = a / a.norm(); b = b / b.norm();
	if(!collinear(point(), a, b)) return 0;
	return zero(a.x - b.x) && zero(a.y - b.y) ? 1 : -1;
}

// CORNER: a == b
struct segment {
	point a, b;

	segment() {}
	segment(point _a, point _b): a(_a), b(_b) {}

	point vec() { return b - a; }

	bool contains(point p) {
		return a == p || b == p || parallel(a-p, b-p) == -1;
	}

	point proj(point p) { // projection of p onto segment
		p = p - a;
		point v = vec();
		return a + v*((p*v)/(v*v));
	}

};

bool intersects(segment r, segment s) {
	if(r.contains(s.a) || r.contains(s.b) || s.contains(r.a) || s.contains(r.b)) return 1;
	return left(r.a, r.b, s.a) != left(r.a, r.b, s.b) && 
		left(s.a, s.b, r.a) != left(s.a, s.b, r.b);
}

bool parallel(segment r, segment s) {
	return parallel(r.vec(), s.vec());
}

point line_intersection(segment r, segment s) {
	if(parallel(r, s)) return point(HUGE_VAL, HUGE_VAL);
	point vr = r.vec(), vs = s.vec();
	double cr = vr ^ r.a, cs = vs ^ s.a;
	return (vs*cr - vr*cs) / (vr ^ vs);
}

struct polygon {
	vector<point> vp;
	int n;

	polygon(vector<point>& _vp): vp(_vp), n(vp.size()) {
		if(area2() < -EPS) reverse(all(_vp));
	}

	int nxt(int i) { return i+1<n ? i+1 : 0; }
	int prv(int i) { return i ? i-1 : 0; }

	// If positive, the polygon is in ccw order. It is in cw order otherwise.
	double area2() { // O(n
		double acum = 0;
		for(int i = 0; i < n; i++)
			acum += vp[i] ^ vp[nxt(i)];
		return acum;
	}

	bool has(point p) { // O(log n). The polygon must be convex and in ccw order
		if(right(vp[0], vp[1], p) || left(vp[0], vp[n-1], p)) return 0;
		int lo = 1, hi = n;
		while(lo + 1 < hi) {
			int mid = (lo + hi) / 2;
			if(!right(vp[0], vp[mid], p)) lo = mid;
			else hi = mid;
		}
		return hi != n ? !right(vp[lo], vp[hi], p) : dist2(vp[0], p) < dist2(vp[0], vp[n-1]) + EPS;
	}

	double calipers() { // O(n). The polygon must be convex and in ccw order.
		double ans = 0;
		for(int i = 0, j = 1; i < n; i++) {
			point v = vp[nxt(i)] - vp[i];
			while((v ^ (vp[nxt(j)] - vp[j])) > EPS) j = nxt(j);
			// do something with vp[i] and vp[j]
			ans = max(ans, dist2(vp[i], vp[j])); // Example with polygon diameter squared
		}
		return ans;
	}

	// returns the maximal point using comparator cmp
	// example: 
	// 	extreme([&](point p, point q) {return p * v > q * v;});
	// 	returns point with maximal dot product with v
	int extreme(const function<bool(point, point)> &cmp) {
		auto is_extreme = [&](int i, bool& cur_dir) -> bool {
			cur_dir = cmp(vp[nxt(i)], vp[i]);
			return !cmp(vp[prv(i)], vp[i]) && !cur_dir;
		};
		bool last_dir, cur_dir;
		if(is_extreme(0, last_dir)) return 0;
		int lo = 0, hi = n; 
		while(lo + 1 < hi) {
			int m = (lo + hi) / 2;
			if(is_extreme(m, cur_dir)) return m;
			bool rel_dir = cmp(vp[m], vp[lo]);
			if((!last_dir && cur_dir) || (last_dir == cur_dir && rel_dir == cur_dir)) {
				lo = m;
				last_dir = cur_dir;
			} else hi = m;
		}
		return lo;
	}

	pair<int, int> tangent(point p) { // O(log n) for convex polygon in ccw orientation
		// Finds the indices of the two tangents to an external point q
		auto left_tangent = [&](point r, point s) -> bool {
			return right(p, r, s);
		};
		auto right_tangent = [&](point r, point s) -> bool {
			return left(p, r, s);
		};
		return {extreme(left_tangent), extreme(right_tangent)};
	}

	void normalize() { // p[0] becomes the lowest leftmost point 
		rotate(vp.begin(), min_element(all(vp)), vp.end());
	}

	polygon operator+(polygon& rhs) { // Minkowsky sum
		normalize();
		rhs.normalize();
		vector<point> sum;
		double dir;
		for(int i = 0, j = 0; i < n*n || j < rhs.n**rhs.n; i += dir > -EPS, j += dir < EPS) {
			sum.push_back(vp[i % n] + rhs.vp[j % rhs.n]);
			dir = (vp[(i + 1) % n] - vp[i % n]) 
				^ (rhs.vp[(j + 1) % rhs.n] - rhs.vp[j % rhs.n]);
		}
		return polygon(sum);
	}
};

#define fi first
#define se second

using ll = long long;

using db = long double;

struct CHT {
    int it;
    vector<ll> a, b;
    CHT():it(0){}
    bool useless(){
        int sz = a.size();
        int r = sz-1, m = sz-2, l = sz-3;
        return (b[l] - b[r]) * (a[m] - a[l]) <= (b[l] - b[m]) * (a[r] - a[l]);
    }
    void add(ll A, ll B){
        a.push_back(A); b.push_back(B);
        while (!a.empty()){
            if ((a.size() < 3) || !useless()) break;
            a.erase(a.end() - 2);
            b.erase(b.end() - 2);
        }
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1), c(n+1);
    vector<int> ok(3*n+1);
    for(int i = 0; i <= n; i++)
        cin >> a[i];
    for(int i = 0; i <= n; i++)
        cin >> b[i];
    for(int i = 0 ; i <= n; i++)
        cin >> c[i];
	
    vector<array<int,2>> sad;
	auto calcmaq = [&](vector<int> v){
		vector<pair<int,int>> mq;
		for(int i = 0; i <= n; i++){
			while(!mq.empty() && mq.back().fi <= v[i]) mq.pop_back();
			mq.push_back({v[i],i});
		}
		return mq;
	};

	auto cross = [&] (pair<int, int> x, pair<int, int> y) {
		return x.first * y.second - y.first * x.second;
	};
	assert (cross ({1, 0}, {1, 1}) > 0);

	auto is_left = [&] (pair<int, int> r1, pair<int, int> r2, pair<int, int> x) {
		// queremos ver se x esta na esquerda de r1, r2

		r2.first -= r1.first;
		r2.second -= r1.second;

		x.first -= r1.first;
		x.second -= r1.second;

		return cross (r2, x) > 0;
	};

	auto fix = [&] (vector<pair<int, int>> points) {
		for (auto &[y, x] : points) swap (y, x);
		sort(points.begin(),points.end());

		vector<pair<int, int>> hull;
		for (auto [x, y] : points) {
			hull.pb ({x, y});

			while (hull.size () > 2) {
				// tenho que ver se o ponto hull[-2] esta na esquerda da reta [hull[-1], hull[-3]]

				pair<int, int> r1 = end (hull)[-1], r2 = end (hull)[-3], X = end (hull)[-2];

				if (is_left (r1, r2, X)) {
					hull.erase (hull.end() - 2);
				}
				else break;
			}
		}

		//for (auto &[x, y] : hull) swap (x, y);
		return hull;
	};

	auto topoint = [&](vector<pair<int,int>> v){
		int k = v.size();
		vector<point> ret(k);
		for(int i = 0; i < k; i++){
			ret[i].x = v[i].fi;
			ret[i].y = v[i].se;
		}
		return ret;
	};

	for(int q = 0; q < 2; q++){
		auto ma = calcmaq(a);
		auto mb = calcmaq(b);
		auto mc = calcmaq(c);
		// for (auto u : ma) cout << u.first << " ";
		// cout << "\n";
		ma = fix (ma);
		mb = fix (mb);
		mc = fix (mc);

		auto poa = topoint(ma);
		auto pob = topoint(mb);
		auto poc = topoint(mc);
		polygon polya(poa);
		polygon polyb(pob);
		polygon polyc(poc);
		polygon polyab = polya+polyb;
		polygon polyabc =polyab+polyc;

		for(auto po : polyabc.vp){
			int eu = round(po.x);
			if(q){
				eu = 3*n-eu;
			}
			int valeu = round(po.y);
			sad.pb({eu,valeu});
		}
		// for (auto u : ma) cout << u.first << " ";
		// cout << "\n";
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		reverse(c.begin(),c.end());
	}
	sad.pb({0,a[0]+b[0]+c[0]});
	sad.pb({3*n,a[n]+b[n]+c[n]});
	sort(sad.begin(),sad.end());
	sort (all (sad));
	sad.resize (unique (all (sad)) - sad.begin ());

	CHT cht;
	for(auto [A,B] : sad){
		cht.add(A,B);
	}
	for(auto fe : cht.a){
		ok[fe] = 1;
	}
	vector<int> ans;
	for(int i = 0; i <= 3*n; i++){
		if(!ok[i]) ans.pb(i);
	}
	cout << ans.size() << '\n';
	for(auto x : ans ) cout << x << ' ';
	cout << '\n';

}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	solve();
}

Details

answer.code: In member function ‘polygon polygon::operator+(polygon&)’:
answer.code:221:60: error: invalid type argument of unary ‘*’ (have ‘int64_t’ {aka ‘long int’})
  221 |                 for(int i = 0, j = 0; i < n*n || j < rhs.n**rhs.n; i += dir > -EPS, j += dir < EPS) {
      |                                                            ^~~~~~