QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#279250 | #7730. Convex Checker | PhantomThreshold | WA | 1ms | 3812kb | C++20 | 2.2kb | 2023-12-08 14:39:54 | 2023-12-08 14:39:55 |
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-12-08 14:39:54]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long double PI = acos(-1);
struct Point{
ll x,y;
};
using Vec = Point;
struct Line{
Point P;Vec v;
};
struct Seg{
Point A,B;
};
int sgn(ll x){
if(x == 0)return 0;
if(x > 0)return 1;
return -1;
}
Vec operator + (const Vec &A,const Vec &B){
return {A.x + B.x,A.y + B.y};
}
Vec operator - (const Vec &A,const Vec &B){
return {A.x - B.x,A.y - B.y};
}
ll operator * (const Vec &A,const Vec &B){
return A.x * B.x + A.y * B.y;
}
ll operator ^ (const Vec &A,const Vec &B){
return A.x * B.y - A.y * B.x;
}
long double len(Vec x){
return sqrt(1.0 * x.x * x.x + 1.0 * x.y * x.y);
}
long double cos_t(Vec u,Vec v){
return 1.0 * (u * v) / len(u) / len(v);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<Point> a(n);
map<pair<int,int>,int> mp;
for(int i = 0;i < n;i ++){
cin >> a[i].x >> a[i].y;
if(mp.find({a[i].x,a[i].y}) != mp.end()){
cout << "No1\n";
return 0;
}
mp[{a[i].x,a[i].y}] = 1;
}
int flag = sgn((a[1] - a[0]) ^ (a[2] - a[1]));
if(flag == 0){
cout << "No2\n";
return 0;
}
for(int i = 1;i < n;i ++){
auto nxt = [&](int x){
return (x + 1) % n;
};
int nxt1 = nxt(i),nxt2 = nxt(nxt1);
int pd = sgn((a[nxt1] - a[i]) ^ (a[nxt2] - a[nxt1]));
if(pd != flag){
cout << "No3\n";
return 0;
}
}
long double sum = 0;
for(int i = 0;i < n;i ++){
auto nxt = [&](int x){
return (x + 1) % n;
};
auto pre = [&](int x){
return (x - 1 + n) % n;
};
int pr = pre(i),nx = nxt(i);
Vec v1 = a[pr] - a[i],v2 = a[nx] - a[i];
// if((v1 * v2) <= 0){
// cout << "No\n";return 0;
// }
long double co = cos_t(v1,v2);
long double ang = acos(co);
sum += ang;
}
long double Ang = 1.0 * (n - 2) * PI;
cerr << Ang << " " << sum << "\n";
if(fabs(Ang - sum) <= 1e-4){
cout << "Yes\n";
}
else cout << "No4\n";
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3812kb
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: 3808kb
input:
4 0 0 0 3 1 2 1 1
output:
Yes
result:
ok answer is YES
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3516kb
input:
3 0 0 0 0 0 0
output:
No1
result:
wrong output format YES or NO expected, but NO1 found