QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249504#7569. LinesUSP_USP_USPWA 2ms3936kbC++209.9kb2023-11-12 11:06:472023-11-12 11:06:48

Judging History

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

  • [2023-11-12 11:06:48]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3936kb
  • [2023-11-12 11:06:47]
  • 提交

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

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

3
3 1 8 7
9 1 3 1
5 1 1 6

output:

5
1 3 4 7 8 

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1
1 2
1 2
1 2

output:

2
1 2 

result:

ok 3 number(s): "2 1 2"

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3936kb

input:

252
336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 527268921 1...

output:

747
1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 1...

result:

wrong answer 1st numbers differ - expected: '733', found: '747'