QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410435 | #7906. Almost Convex | chenxinyang2006# | WA | 8ms | 3872kb | C++20 | 2.7kb | 2024-05-13 23:54:36 | 2024-05-13 23:54:37 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n;
ll _x[2005],_y[2005];
ll cross(int i,int j,int k){//i->k 这条相比 i->j,是否是向左转的
return (_x[j] - _x[i]) * (_y[k] - _y[i]) - (_x[k] - _x[i]) * (_y[j] - _y[i]);
}
ll calc(ll x1,ll y1,ll x2,ll y2){
return x1 * y2 - x2 * y1;
}
int C,ord[2005],rk[2005],cov[2005];
bool cmp(int x,int y){
return cross(C,x,y) >= 0;
}
void prt(int id){
printf("(%lld,%lld) ",_x[id],_y[id]);
}
int k,answer;
void slv(int x,int y){
// printf("slv ");prt(x);prt(y);
// printf("\n");
C = x;
sort(ord + 1,ord + k + 1,cmp);
rep(i,1,k) rk[ord[i]] = i;
// rep(i,1,k) prt(ord[i]);
// printf("\n");
// printf("cross=%lld ",cross(2,3,5));
C = y;
sort(ord + 1,ord + k + 1,cmp);
int qwq = 0;
rep(i,1,k){
if(rk[ord[i]] > qwq){
qwq = rk[ord[i]];
answer++;
}
}
// rep(i,1,k) prt(ord[i]);
// printf("\n");
}
vector <int> sta;
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&n);
C = 1;
rep(i,1,n) scanf("%lld%lld",&_x[i],&_y[i]);
rep(i,1,n) if(_y[i] < _y[C] || (_y[i] == _y[C] && _x[i] < _x[C])) C = i;
// prt(C);
ord[++k] = C;
rep(i,1,n) if(i != C) ord[++k] = i;
sort(ord + 2,ord + n + 1,cmp);
// rep(i,1,n) prt(ord[i]);
// printf("\n");
rep(_i,1,n){
int w = ord[_i],u,v;
while(SZ(sta) >= 2){
// printf("awa\n");
v = sta.back();
u = sta[SZ(sta) - 2];
if(calc(_x[w] - _x[v],_y[w] - _y[v],_x[v] - _x[u],_y[v] - _y[u]) > 0){
// printf("pop ");
// prt(v);
sta.pop_back();
}else{
break;
}
}
sta.eb(w);
}
// printf("conv hull\n");
// for(int u:sta) prt(u);
// printf("\n");
k = 0;
for(int u:sta) cov[u] = 1;
rep(u,1,n) if(!cov[u]) ord[++k] = u;
answer = 1;
rep(i,0,SZ(sta) - 2) slv(sta[i],sta[i + 1]);
slv(sta[0],sta.back());
printf("%d\n",answer);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 8ms
memory: 3872kb
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...
output:
18645
result:
wrong answer 1st numbers differ - expected: '718', found: '18645'