QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#312709 | #7730. Convex Checker | EndPB | WA | 12ms | 34992kb | C++17 | 2.9kb | 2024-01-24 11:00:20 | 2024-01-24 11:00:20 |
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;
}
inline int nxt(int x, int n) {
return x == n ? 1 : x + 1;
}
Point ord_p[N], ord_stk[N];
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);
// for (int i = 1; i <= tp; ++i) stk[i].out();
if (tp == n) {
for (int i = 1; i <= n; ++i) {
ord_p[i] = p[nxt(i, n)] - p[i];
ord_stk[i] = stk[nxt(i, n)] - stk[i];
}
sort(ord_p + 1, ord_p + n + 1, cmpb);
sort(ord_stk + 1, ord_stk + n + 1, cmpb);
for (int i = 1; i <= n; ++i) {
if (!(ord_p[i] == ord_stk[i])) {
cout << "No";
return 0;
}
}
cout << "Yes";
} else cout << "No";
}
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 34992kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 12ms
memory: 34972kb
input:
4 0 0 0 1 1 1 1 0
output:
Yes
result:
ok answer is YES
Test #3:
score: -100
Wrong Answer
time: 8ms
memory: 34904kb
input:
4 0 0 0 3 1 2 1 1
output:
No
result:
wrong answer expected YES, found NO