QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#249514 | #7569. Lines | USP_USP_USP | TL | 0ms | 0kb | C++20 | 10.0kb | 2023-11-12 11:19:11 | 2023-11-12 11:19:11 |
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;
int last = 0;
for(int i = 0, j = 0; i < n || j < 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]);
if(abs(dir) < EPS){
dir = -10;
}
}
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: 0
Time Limit Exceeded
input:
3 3 1 8 7 9 1 3 1 5 1 1 6