QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#258131 | #7730. Convex Checker | 552Hz | WA | 0ms | 3980kb | C++14 | 5.1kb | 2023-11-19 15:25:58 | 2023-11-19 15:25:58 |
Judging History
你现在查看的是最新测评结果
- [2024-07-04 19:27:17]
- hack成功,自动添加数据
- (/hack/727)
- [2024-07-04 19:17:30]
- hack成功,自动添加数据
- (/hack/726)
- [2023-12-08 14:40:48]
- hack成功,自动添加数据
- (//qoj.ac/hack/493)
- [2023-11-19 15:25:58]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
typedef double db;
const db EPS = 1e-5;
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const {
int c = cmp(x, p.x);
if (c) return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
db distTo(P p) { return (*this-p).abs(); }
db alpha() { return atan2(y, x); }
void read() { cin>>x>>y; }
void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
db abs() { return sqrt(abs2());}
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);}
P unit() { return *this/abs(); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
P rot(db an){ return {x*cos(an) - y*sin(an),x*sin(an) + y*cos(an)}; }
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
// 直线 p1p2, q1q2 是否恰有一个交点
bool chkLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return sign(a1+a2) != 0;
}
// 求直线 p1p2, q1q2 的交点
P isLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
// 判断区间 [l1, r1], [l2, r2] 是否相交
bool intersect(db l1,db r1,db l2,db r2){
if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2);
return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}
// 线段 p1p2, q1q2 相交
bool isSS(P p1, P p2, P q1, P q2){
return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) &&
crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) <= 0;
}
// 线段 p1p2, q1q2 严格相交
bool isSS_strict(P p1, P p2, P q1, P q2){
return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) < 0;
}
// m 在 a 和 b 之间
bool isMiddle(db a, db m, db b) {
/*if (a > b) swap(a, b);
return cmp(a, m) <= 0 && cmp(m, b) <= 0;*/
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b) {
return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
// 点 p 在线段 p1p2 上
bool onSeg(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
// q1q2 和 p1p2 的交点 在 p1p2 上?
// 点 p 严格在 p1p2 上
bool onSeg_strict(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
// 求 q 到 直线p1p2 的投影(垂足) ⚠️ : p1 != p2
P proj(P p1, P p2, P q) {
P dir = p2 - p1;
return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q 以 直线p1p2 为轴的反射
P reflect(P p1, P p2, P q){
return proj(p1,p2,q) * 2 - q;
}
// 求 q 到 线段p1p2 的最小距离
db nearest(P p1, P p2, P q){
if (p1 == p2) return p1.distTo(q);
P h = proj(p1,p2,q);
if(isMiddle(p1,h,p2))
return q.distTo(h);
return min(p1.distTo(q),p2.distTo(q));
}
// 求 线段p1p2 与 线段q1q2 的距离
db disSS(P p1, P p2, P q1, P q2){
if(isSS(p1,p2,q1,q2)) return 0;
return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
vector<P> convexHull(vector<P> ps) {
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
qs.resize(k - 1);
return qs;
}
vector<P> convexHullNonStrict(vector<P> ps) {
//caution: need to unique the Ps first
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
qs.resize(k - 1);
return qs;
}
void solve(){
int n;
vector<P> ans;
cin>>n;
for(int i=1;i<=n;i++){
P x;
x.read();
ans.push_back(x);
}
ans.erase(unique(ans.begin(),ans.end()),ans.end());
if(ans.size()==1){
cout<<"No";
return;
}
set<P>sq;
vector<P> node=convexHull(ans);
for(auto x:node){
sq.insert(x);
}
bool flag=1;
for(auto x:ans){
if(!sq.count(x)){
flag=0;
break;
}
}
if(flag){
cout<<"Yes";
}else{
cout<<"No";
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3980kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3944kb
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: 3752kb
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: 3880kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3768kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES