QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341282#7730. Convex CheckerZeardoe#WA 1ms4172kbC++142.6kb2024-02-29 17:20:252024-02-29 17:20:28

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-02-29 17:20:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4172kb
  • [2024-02-29 17:20:25]
  • 提交

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