QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73089 | #5155. Faster Than Light | Sorting | WA | 164ms | 37132kb | C++ | 6.1kb | 2023-01-22 00:15:20 | 2023-01-22 00:15:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> int sgn(T x){ return (x > 0) - (x < 0); }
template<class T>
struct Point{
typedef Point P;
T x, y;
explicit Point(T x = 0, T y = 0): x(x), y(y){}
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y);}
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator-(P p) const {return P(x - p.x, y - p.y);}
P operator+(P p) const {return P(x + p.x, y + p.y);}
T cross(P p) const {return x * p.y - y * p.x;}
T dot(P p) const {return x * p.x + y * p.y; }
T cross(P a, P b) const {return (a - *this).cross(b - *this);}
};
struct Angle{
ll x, y;
ll t;
Angle(ll x, ll y, ll t = 0): x(x), y(y), t(t){}
Angle(Point<ll> p): x(p.x), y(p.y), t(0){}
int half() const {
assert(x || y);
return y < 0 || (y == 0 && x < 0);
}
};
bool operator<(Angle a, Angle b){
return make_tuple(a.t, a.half(), a.y * b. x) <
make_tuple(b.t, b.half(), a.x * b.y);
}
const int N = 2e5 + 3;
int n;
ll x1[N], yedno[N], x2[N], y2[N];
#define all(x) (x).begin(), (x).end()
typedef Point<ll> P;
vector<P> convexHull(vector<P> pts) {
if(pts.size() <= 1) return pts;
sort(all(pts));
vector<P> h((int)pts.size() + 1);
int s = 0, t = 0;
for(int it = 2; it--; s = --t, reverse(all(pts))){
for(P p: pts){
while(t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--;
h[t++] = p;
}
}
return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}
template<class P>
int sideOf(P s, P e, P p){ return sgn(s.cross(e, p)); }
bool onSegment(P s, P e, P p){
return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}
bool inHull(const vector<P> &l, P p, bool strict = true){
int a = 1, b = (int)l.size() - 1, r = !strict;
if(l.size() < 3) return r && onSegment(l[0], l.back(), p);
if(sideOf(l[0], l[a], l[b]) > 0) swap(a, b);
if(sideOf(l[0], l[a], p) >= r || sideOf(l[0], l[b], p) <= -r)
return false;
while(abs(a - b) > 1){
int c = (a + b) / 2;
(sideOf(l[0], l[c], p) > 0 ? b : a) = c;
}
return sgn(l[a].cross(l[b], p)) < r;
}
bool inPolygon(const vector<P> &p, P a, bool strict = true){
int cnt = 0, n = p.size();
for(int i = 0; i < n; ++i){
P q = p[(i + 1) % n];
if(onSegment(p[i], q, a)) return !strict;
cnt ^= ((a.y < p[i].y) - (a.y < q.y)) * a.cross(p[i], q) > 0;
}
return cnt;
}
/*template<class P> vector<P> segInter(P a, P b, P c, P d){
auto oa = c.cross(d, a), ob = c.cross(d, b),
oc = a.cross(b, c), od = a.cross(b, d);
if(sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0)
return {(a * ob - b * oa) / (ob - oa)};
set<P> s;
if(ons)
}*/
bool check_ch(const vector<Point<ll>> &ch1, const vector<Point<ll>> &ch2){
for(int i = 0; i < ch2.size(); ++i){
int nxt = (i + 1) % n;
if(sideOf(ch2[i], ch2[nxt], ch1[1]) * sideOf(ch2[i], ch2[nxt], ch1[1]) == -1)
return false;
}
if(inPolygon(ch2, ch1[0], false) && inPolygon(ch2, ch1[1], false))
return false;
return true;
}
bool check(const vector<Point<ll>> &in, vector<Point<ll>> out){
if(n <= 100){
for(int i = 0; i < in.size(); ++i)
for(int j = 0; j < out.size(); ++j){
bool ok = true;
for(int k = 0; k < in.size(); ++k)
ok &= sideOf(in[i], out[j], in[k]) <= 0;
for(int k = 0; k < out.size(); ++k)
ok &= sideOf(in[i], out[j], out[k]) >= 0;
if(ok)
return true;
ok = true;
for(int k = 0; k < in.size(); ++k)
ok &= sideOf(in[i], out[j], in[k]) >= 0;
for(int k = 0; k < out.size(); ++k)
ok &= sideOf(in[i], out[j], out[k]) <= 0;
if(ok)
return true;
}
return false;
}
vector<Point<ll>> ch1 = convexHull(in);
for(auto &p: out)
p = Point<ll>{-p.x, -p.y};
vector<Point<ll>> ch2 = convexHull(out);
// for(auto [x, y]: ch1)
// cout << x << "," << y << " ";
// cout << endl;
// cout << "Ch2 ";
// for(auto [x, y]: ch2)
// cout << x << "," << y << " ";
// cout << endl;
if(ch1.size() == 2){
return check_ch(ch1, ch2);
}
if(ch2.size() == 2)
return check_ch(ch2, ch1);
ch1.push_back(ch1[0]);
ch2.push_back(ch2[0]);
int i = 1, j = 1;
vector<Point<ll>> v;
v.push_back(ch1[0] + ch2[0]);
while(i < ch1.size() && j < ch2.size()){
Angle a1(ch1[i] - ch1[i - 1]);
Angle a2(ch2[j] - ch2[j - 1]);
if(a1 < a2){
v.push_back(v.back() + ch1[i] - ch1[i - 1]);
++i;
}
else{
v.push_back(v.back() + ch2[j] - ch2[j - 1]);
++j;
}
}
while(i < ch1.size()){
v.push_back(v.back() + ch1[i] - ch1[i - 1]);
++i;
}
while(j < ch2.size()){
v.push_back(v.back() + ch2[j] - ch2[j - 1]);
++j;
}
v.pop_back();
// cout << "v: ";
// for(auto [x, y]: v)
// cout << x << "," << y << " ";
// cout << endl;
return !inPolygon(v, Point<ll>(0, 0), true);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; ++i)
cin >> x1[i] >> yedno[i] >> x2[i] >> y2[i];
if(n <= 2){
cout << "possible\n";
return 0;
}
vector<Point<ll>> in1, in2, out1, out2;
for(int i = 0; i < n; ++i){
in1.push_back(Point<ll>(x1[i], yedno[i]));
in2.push_back(Point<ll>(x1[i], y2[i]));
out1.push_back(Point<ll>(x2[i], y2[i]));
out2.push_back(Point<ll>(x2[i], yedno[i]));
}
if(check(in1, out1) || check(in2, out2))
cout << "possible\n";
else
cout << "impossible\n";
}
/*
3
1 1 2 2
2 2 3 3
3 3 4 4
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9612kb
input:
5 1 3 3 4 2 2 4 3 4 1 5 3 5 2 7 3 6 3 8 4
output:
possible
result:
ok single line: 'possible'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7456kb
input:
4 1 1 2 2 1 3 2 4 3 1 4 2 3 3 4 4
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 7476kb
input:
3 1 1 2 2 1 3 2 4 3 3 4 4
output:
possible
result:
ok single line: 'possible'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7460kb
input:
5 0 0 1 999999999 0 999999999 999999999 1000000000 1 0 999999998 1 999999998 0 999999999 999999999 2 999999998 3 999999999
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7568kb
input:
4 0 1 1 1000000000 1 0 999999999 1 999999999 0 1000000000 999999999 2 999999999 999999999 1000000000
output:
possible
result:
ok single line: 'possible'
Test #6:
score: 0
Accepted
time: 0ms
memory: 7432kb
input:
3 0 0 1 1000000000 2 0 999999999 1 2 999999999 999999999 1000000000
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
3 0 0 1 1000000000 2 0 999999999 1 2 999999999 1000000000 1000000000
output:
possible
result:
ok single line: 'possible'
Test #8:
score: -100
Wrong Answer
time: 164ms
memory: 37132kb
input:
199999 433914929 216935871 433914930 216935872 621822279 310889546 621822280 310889547 395914333 197935573 395914334 197935574 582775641 291366227 582775642 291366228 658726133 329341473 658726134 329341474 71689261 35823037 71689262 35823038 453260967 226608890 453260968 226608891 249802825 1248798...
output:
possible
result:
wrong answer 1st lines differ - expected: 'impossible', found: 'possible'