QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#685789#8814. Almost Convex 2CrysflyWA 636ms4656kbC++145.0kb2024-10-28 21:19:222024-10-28 21:19:27

Judging History

This is the latest submission verdict.

  • [2024-10-28 21:19:27]
  • Judged
  • Verdict: WA
  • Time: 636ms
  • Memory: 4656kb
  • [2024-10-28 21:19:22]
  • Submitted

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

typedef double db;
const db eps=1e-8,pi=3.14159265358979323846;
int sgn(int x){return x<0?-1:x>0;}
int cmp(int a,int b){return sgn(a-b);}

struct P{
	int x,y,id;
	P(int x=0,int y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(int o){return x*=o,y*=o,*this;}
	P&operator /=(int o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,int b){return a*=b;}
	friend P operator /(P a,int b){return a/=b;}
	friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
	friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
	friend bool operator !=(P a,P b){return !(a==b);}
	friend int operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend int operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	
	P rot90(){return P(-y,x);}
	db ang(){return atan2(y,x);}
	db len(){return sqrt(x*x+y*y);}
	int len2(){return x*x+y*y;}
	
	int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
//	P unit(){return ((*this))/len();}
	
	void read(){cin>>x>>y;}
	void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
	if(a.half()!=b.half())return a.half()<b.half();
	return sgn(a*b)>0;
}

db dis(P a,P b){return (a-b).len();}
int cross(P a,P b,P c){
	// (a->b)*(a->c)
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
	return sgn(cross(a,b,c));
}

vector<P>convex(vector<P>a){
	int n=a.size(),m=0; if(n<=1)return a;
	sort(a.begin(),a.end());
	vector<P>st(n*2); int tp=0;
	For(i,0,n-1){
		while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	int t=tp;
	Rep(i,n-2,0){
		while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	st.resize(tp-1);
	return st;
}

bool in_tri(P a,P b,P c,P p){
	if(cmp3(a,b,c)<0) swap(b,c);
	return cmp3(a,b,p)>=0 && cmp3(b,c,p)>=0 && cmp3(c,a,p)>=0;
}

#define maxn 505
#define inf 0x3f3f3f3f

int n,m1,m2;
P p[maxn];
vector<P>h,in;
bool vis[maxn];
int cnt[maxn][maxn];

bool chk(int i,int j,int k){
	For(x,1,n) if(x!=i&&x!=j&&x!=k && in_tri(p[i],p[j],p[k],p[x])) return 1;
	return 0; 
	return cnt[i][j]+cnt[j][k]+cnt[k][i]!=0;
}

ll res;

bool hav[maxn][maxn];
bool col[maxn];

bool isseg_s(P p1,P p2,P q1,P q2){
	return cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<0;
}

signed main()
{
	n=read();
	For(i,1,n) p[i].x=read(),p[i].y=read();
	sort(p+1,p+n+1);
	For(i,1,n) p[i].id=i,h.pb(p[i]);
	
	h=convex(h);
	for(auto it:h) vis[it.id]=1;
	For(i,1,n) if(!vis[i]) in.pb(p[i]);
	
	For(i,2,n) For(j,i+1,n) {
		For(k,2,n) if(k!=i && k!=j) cnt[i][j]+=in_tri(p[1],p[i],p[j],p[k]);
		cnt[j][i]=cnt[i][j];
		if(cmp3(1,i,j)>0) cnt[j][i]=-cnt[j][i];
		else cnt[i][j]=-cnt[i][j];
	}
	
	m1=h.size();
	m2=in.size();
	res=1;
	For(i,0,m1-1){
		For(j,0,m2-1){
			hav[i][j]=chk(h[i].id,h[(i+1)%m1].id,in[j].id);
			if(!hav[i][j]) ++res;
		}
	}
	
//	cout<<"cut1 "<<res<<"\n";
//	cout<<"sz "<<m1<<" "<<m2<<"\n";
	
	int now2=0;
	For(i,0,m1-1){
		For(j,0,m2-1) if(!hav[i][j]) {
			int u=h[i].id,v=h[(i+1)%m1].id,w=in[j].id;
			For(k,0,m2-1) if(j!=k) {
			//	if((!chk(u,w,in[k].id))) cout<<"add "<<u<<" "<<w<<" "<<in[k].id<<"\n";
			//	if((!chk(v,w,in[k].id))) cout<<"add "<<v<<" "<<w<<" "<<in[k].id<<"\n";
				for(auto x:{u,v}){
					if(!chk(x,w,in[k].id) && !isseg_s(p[x^u^v],p[w],p[x],in[k])){
						++res;
						if(!in_tri(p[u],p[v],in[k],p[w])) ++now2;//cout<<"Add2 "<<u<<" "<<v<<" "<<in[k].id<<" "<<w<<"\n";
					}
				}
			}
		}
	}
//	cout<<"now2 "<<now2<<"\n";
	res-=now2/2;
	
//	cout<<"cut2 "<<res<<"\n";
	
	For(i,0,m2-1)
		For(j,0,m2-1) if(i!=j) {
			int now=0;
			For(k,0,m1-1) {
				col[k]=cmp3(in[i],in[j],h[k])>0;
			}
			For(k,0,m1-1){
				if(col[k]==0) now+=(!hav[k][j]);
			}
//			cout<<"i,j "<<i<<" "<<j<<"\n";
//			For(k,0,m1-1) cout<<col[k]<<" "; cout<<" col\n";
			For(k,0,m1-1) if(col[k] && !col[(k+m1-1)%m1]) {
				while(col[k]) {
					if(!col[(k+1)%m1] && i>j) break;
//					cout<<"k,now "<<k<<" "<<now<<"\n";
					if(!hav[k][i]) res+=now;
					now+=(!hav[k][j]);
					k=(k+1)%m1;
				}
				break;
			}
		}
	
	cout<<res;
	return 0;
}

/*

9
0 2
1 0
1 3
2 1
2 5
3 0
3 3
4 2
5 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

input:

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

output:

26

result:

ok 1 number(s): "26"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

13

result:

ok 1 number(s): "13"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

20

result:

ok 1 number(s): "20"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3608kb

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: 636ms
memory: 4656kb

input:

500
-5276 -1176
3417 -883
-6586 -1581
4425 7450
-7896 -3039
-6316 2357
5464 2109
-3428 -6184
-1477 -1383
-5288 -969
-5528 -4316
-508 -364
-7424 -4848
-1073 -9882
4320 -862
-4720 -2569
560 -5594
-4492 -7290
3629 9120
3112 5970
-2587 -4693
7147 -6919
-935 8748
2664 4405
-6865 -3149
8844 -4641
-3706 -9...

output:

54047

result:

wrong answer 1st numbers differ - expected: '50930', found: '54047'