QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312665 | #7730. Convex Checker | EndPB | WA | 0ms | 16288kb | C++17 | 2.3kb | 2024-01-24 10:14:59 | 2024-01-24 10:14:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long double
#define ld ll
#define Vector Point
#define S(x) (x)*(x)
#define N 200010
const int Kep = 1;
const ld eps = 1e-8, pi = acosl(-1.0), Mn = powl(10.0, -Kep);
inline int sign(ld a) { return a < -eps ? -1 : (a > eps ? 1 : 0); }
inline ld Abs(ld a) { return a * sign(a); }//取绝对值
inline void Out(ld a, int k = Kep) {
if (-Mn < a && a < Mn) a = 0;
cout << fixed << setprecision(Kep) << a;//<iomanip>
}
struct Point {
ld x, y;
Point(ld a = 0, ld b = 0) { x = a, y = b; }
inline void in() { cin >> x >> y; }
inline void out() {
Out(x);
cout << " ";
Out(y);
cout << endl;
}
};
inline ld Dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }//【点积】
inline ld Cro(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }//【叉积】
inline ld Len(Vector a) { return sqrtl(Dot(a, a)); }//【模长】
inline ld Angle(Vector a, Vector b) { return acosl(Dot(a, b) / Len(a) / Len(b)); }//【两向量夹角】
inline Vector Normal(Vector a) { return Vector(-a.y, a.x); }//【法向量】
inline Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
inline Vector operator-(Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
inline Vector operator*(Vector a, ld b) { return Vector(a.x * b, a.y * b); }
inline bool operator==(Point a, Point b) { return !sign(a.x - b.x) && !sign(a.y - b.y); }//两点坐标重合则相等
Point stk[N];
int tp = 0;
Point p[N];
bool cmpb(Point a, Point b) {
return Abs(a.x - b.x) < eps ? a.y < b.y : a.x < b.x;
}
inline int Andrew(Point *p, int n, Point *stk) {//点的存储位置[1,n]
sort(p + 1, p + 1 + n, cmpb);
int tp = 0;
for (int i = 1; i <= n; ++i) {
while (tp > 1 && sign(Cro(stk[tp] - stk[tp - 1], p[i] - stk[tp - 1])) <= 0) --tp;
stk[++tp] = p[i];
}
int k = tp;
for (int i = n - 1; i >= 1; --i) {
while (tp > k && sign(Cro(stk[tp] - stk[tp - 1], p[i] - stk[tp - 1])) <= 0) --tp;
stk[++tp] = p[i];
}
return --tp;
}
int main() {//Andrew 169ms
int n;
cin >> n;
for (int i = 1; i <= n; ++i) p[i].in();
tp = Andrew(p, n, stk);
if (tp == n) cout << "Yes";
else cout << "No";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16152kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 16288kb
input:
4 0 0 0 1 1 1 1 0
output:
Yes
result:
ok answer is YES
Test #3:
score: 0
Accepted
time: 0ms
memory: 16268kb
input:
4 0 0 0 3 1 2 1 1
output:
Yes
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 0ms
memory: 16240kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 16252kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES