QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73076 | #5155. Faster Than Light | Sorting# | WA | 3ms | 7560kb | C++ | 2.9kb | 2023-01-21 22:14:00 | 2023-01-21 22:14:03 |
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);}
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);}
};
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 check(const vector<Point<ll>> &in, const vector<Point<ll>> &out){
vector<Point<ll>> ch = convexHull(in);
while(ch.size() > 2){
int i = ch.size() - 3;
if(ch[i].cross(ch[i + 1], ch[i + 2]) == 0){
swap(ch[i + 1], ch[i + 2]);
ch.pop_back();
}
else
break;
}
for(auto p: out){
if(inHull(ch, p, true))
return false;
}
return 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: 2ms
memory: 7480kb
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: 7472kb
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: 3ms
memory: 7460kb
input:
3 1 1 2 2 1 3 2 4 3 3 4 4
output:
possible
result:
ok single line: 'possible'
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 7560kb
input:
5 0 0 1 999999999 0 999999999 999999999 1000000000 1 0 999999998 1 999999998 0 999999999 999999999 2 999999998 3 999999999
output:
possible
result:
wrong answer 1st lines differ - expected: 'impossible', found: 'possible'