QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312686 | #7730. Convex Checker | EndPB | WA | 3ms | 22576kb | C++17 | 2.5kb | 2024-01-24 10:43:44 | 2024-01-24 10:43:45 |
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], tmp[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(), tmp[i] = p[i];
tp = Andrew(tmp, n, stk);
if (tp == n) {
for (int i = 1; i < n; ++i)
if (!(p[i + 1] - p[i] == stk[i + 1] - stk[i])) {
cout << "No";
return 0;
}
cout << "Yes";
} else cout << "No";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 22476kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 22576kb
input:
4 0 0 0 1 1 1 1 0
output:
No
result:
wrong answer expected YES, found NO