QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#410435#7906. Almost Convexchenxinyang2006#WA 8ms3872kbC++202.7kb2024-05-13 23:54:362024-05-13 23:54:37

Judging History

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

  • [2024-05-13 23:54:37]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3872kb
  • [2024-05-13 23:54:36]
  • 提交

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;
}

詳細信息

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'