QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276890#7906. Almost ConvexRedcrown#WA 1ms3736kbC++173.6kb2023-12-06 12:21:132023-12-06 12:21:13

Judging History

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

  • [2023-12-06 12:21:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3736kb
  • [2023-12-06 12:21:13]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=4e3+5;
int n,m;
inline int red(){
	int data=0;bool w=0;char ch=getchar();
	while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
	if(ch=='-') w=1,ch=getchar();
	while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
	return w?-data:data;
}
struct point{
	ll x,y;
	bool tp;
	point(){}
	point(ll a,ll b):x(a),y(b){}
	void in(){
		scanf("%lld%lld",&x,&y);
	}
	void out(){
		printf("x:%lld y:%lld\n",x,y);
	}
	point operator -(const point &a)const{
		return point(x-a.x,y-a.y);
	}
	ll operator ^(const point &a)const{
		return x*a.y-y*a.x;
	}
	ll operator *(const point &a)const{
		return x*a.x+y*a.y;
	}
	bool operator <(const point &a)const{
		return x<a.x||(x==a.x&&y<a.y);
	}
	int toleft(const point &a)const{
		const ll t=(*this)^a;
		return (t>0)-(t<0);
	}
	bool operator ==(const point &a)const{
		return x==a.x&&y==a.y;
	}
};
ll judge,cvxs[N],cvxindx[N];
vector <point> points,ans;
bool cmp(ll x,ll y){
	return points[x]<points[y];
}
ll convexhall(vector <point> &points, ll n, vector <point> &ans){
	ll i,sz=0,k,a,x,no,flag=0,ok=1;
	for(i=1;i<=n;i++) cvxindx[i]=i;
	sort(cvxindx+1,cvxindx+n+1,cmp);
	for(i=1;i<=n;i++){
		a=cvxindx[i];
		no=0;
		while(sz>1){
			x=(points[cvxs[sz-2]]-points[cvxs[sz-1]]).toleft(points[a]-points[cvxs[sz-1]]);
			if(x==0) no=1;
			if(x>=0){
				sz--;
				if(sz<flag)flag=0;
			}else{
				break;
			}
		}
		if(no&&!flag) flag=sz+1;
		cvxs[sz++]=a;
	}
	k=sz;
	if(flag) ok=0;
	flag=0;
	for(i=max(1ll,n-1);i>=1;i--){
		a=cvxindx[i];
		no=0;
		while(sz>k){
			x=(points[cvxs[sz-2]]-points[cvxs[sz-1]]).toleft(points[a]-points[cvxs[sz-1]]);
			if(x==0) no=1;
			if(x>=0){
				sz--;
				if(sz<flag) flag=0;
			}else{
				break;
			}
		}
		if(no&&!flag) flag=sz+1;
		cvxs[sz++]=a;
	}
	if(flag) ok=0;
	judge=ok;
	ans.resize(sz+1);
	for(i=1;i<=sz;i++) ans[i]=points[cvxs[i-1]];
	return sz-1;
}
int fans;
bool check(point a,int sze){
	for(int i=1;i<=sze;i++){
		if(a==ans[i]) return 1;
//		if(((ans[i]-ans[i-1])^(a-ans[i-1]))==0){
//			return 1;
//		}
	}
	return 0;
}
ll indx[N],nowpos;
bool cmp1(ll x,ll y){
	int flag1=(points[x].y<points[nowpos].y||(points[x].y==points[nowpos].y&&points[x].x<points[nowpos].x));
	int flag2=(points[y].y<points[nowpos].y||(points[y].y==points[nowpos].y&&points[y].x<points[nowpos].x));
	if(flag1!=flag2){
		return flag1<flag2;
	}else{
		return (points[x]-points[nowpos]).toleft(points[y]-points[nowpos])==1;
	}
}
void solve(){
	fans=1;
	scanf("%d",&n);
	points.resize(n+1);
	for(int i=1;i<=n;i++){
		points[i].in();
	}
	int sze=convexhall(points, n, ans);
	ans[0]=ans[sze];
//	for(int i=1;i<=sze;i++){
//		ans[i].out();
//	}
	for(int i=1;i<=n;i++){
		if(!check(points[i],sze)){
			points[i].tp=1;
		}else{
			points[i].tp=0;
		}
	}
	for(int i=1,tot;i<=n;i++){
		if(!points[i].tp){
			continue;
		}
		nowpos=i;
		tot=0;
		for(int j=1;j<=n;j++){
			if(j==i) continue;
			indx[++tot]=j;	
		}
		sort(indx+1,indx+tot+1,cmp1);
		indx[0]=indx[tot];
//		printf("P: ");
		points[i].out();
		for(int j=1;j<=tot;j++){
//			printf("%d[%d] %d[%d]\n",j,points[indx[j]].tp,j-1,points[indx[j-1]].tp);
			points[indx[j]].out();
			points[indx[j-1]].out();
			if(!points[indx[j]].tp&&!points[indx[j-1]].tp){
				fans++;
			}
		}
//		printf("\n");
	}
	printf("%d\n",fans);
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0); 
	int T=1;
	while(T--)solve();
	return 0;
}
/*
  7
  1 4
  4 0
  2 3
  3 1
  3 5
  0 0
  2 4
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3736kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

x:2 y:3
x:3 y:5
x:4 y:0
x:2 y:4
x:3 y:5
x:1 y:4
x:2 y:4
x:0 y:0
x:1 y:4
x:3 y:1
x:0 y:0
x:4 y:0
x:3 y:1
x:3 y:1
x:3 y:5
x:4 y:0
x:2 y:4
x:3 y:5
x:2 y:3
x:2 y:4
x:1 y:4
x:2 y:3
x:0 y:0
x:1 y:4
x:4 y:0
x:0 y:0
x:2 y:4
x:3 y:5
x:4 y:0
x:1 y:4
x:3 y:5
x:0 y:0
x:1 y:4
x:2 y:3
x:0 y:0
x:3 y:1
x:2 y:3
x:4 ...

result:

wrong output format Expected integer, but "x:2" found