QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#341282 | #7730. Convex Checker | Zeardoe# | WA | 1ms | 4172kb | C++14 | 2.6kb | 2024-02-29 17:20:25 | 2024-02-29 17:20:28 |
Judging History
answer
/*
[templates]:
duipai
compre
addhis
floor_sum
matrix
network_flow
inter
polynomial
subset poly
lca
bitset
valuesgt
fenwick
erbitree
segment
mcmf
primal_dual
centroid
add0cnt
euler
basis
phi
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef array<int, 2> aii;
typedef array<int, 3> aiii;
const int inf = 1e18;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; }
reverse(s.begin(), s.end()); cerr << s << endl;
return;
}
double runtime() {return 1.0*clock()/CLOCKS_PER_SEC;}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍!
//use std::array.
const int N=2e5;
int n;
struct node {int x,y;double ang;} a[N+10];
vector<int> tb;
int cross(aii x,aii y) {
return x[0]*y[1]-x[1]*y[0];
}
bool judge(node x,node y,node z) {
return cross({x.x-y.x,x.y-y.y},{z.x-y.x,z.y-y.y})>=0;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//freopen("X.in","r",stdin);
//freopen("X.out","w",stdout);
//freopen("X.ear","w",stderr);
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
cin>>n; f(i,1,n)cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,[&](node x,node y) {return (x.x<y.x)||(x.x==y.x&&x.y<y.y);});
f(i,2,n)a[i].ang=atan2(a[i].y-a[1].y,a[i].x-a[1].x);
sort(a+2,a+n+1,[&](node x,node y) {return x.ang<y.ang;});
tb.push_back(1);
f(i,2,n) {
while(tb.size() >= 2) {
if(judge(a[*prev(--tb.end())],a[tb.back()],a[i])) tb.pop_back();
else break;
}
tb.push_back(i);
}
if(tb.size()==n) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3756kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 4016kb
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: 3980kb
input:
4 0 0 0 3 1 2 1 1
output:
Yes
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 4172kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES