QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685828#8814. Almost Convex 2CrysflyTL 988ms4880kbC++145.3kb2024-10-28 21:29:462024-10-28 21:29:47

Judging History

This is the latest submission verdict.

  • [2024-10-28 21:29:47]
  • Judged
  • Verdict: TL
  • Time: 988ms
  • Memory: 4880kb
  • [2024-10-28 21:29:46]
  • 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];
int sum[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,m1-1){
		sum[i]=0;
		For(j,0,m2-1) if(!hav[i][j]) ++sum[i];
		res+=sum[i]*(sum[i]-1)/2;
	}
	For(i,0,m1-1) For(j,i+1,m1-1) res+=sum[i]*sum[j];
//	cout<<"res "<<res<<"\n";
	For(i,0,m2-1){
		int ss=0;
		For(j,0,m1-1) if(!hav[j][i]) ++ss;
		res-=ss*(ss-1)/2;
	}
	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]==1) 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(!hav[k][i]) res-=now;//cout<<"sub "<<k<<" "<<now<<"\n";
					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
*/

詳細信息

Test #1:

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

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: 0ms
memory: 3576kb

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: 3516kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 3568kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 643ms
memory: 4820kb

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:

50930

result:

ok 1 number(s): "50930"

Test #7:

score: 0
Accepted
time: 502ms
memory: 4872kb

input:

500
8598 4438
6327 -913
-4037 -1025
7337 -4117
-3092 1011
378 -7033
-8724 4431
-4868 5150
911 529
5509 -1362
1086 -7919
9778 1261
-3832 3610
-3470 7906
-8559 5595
-8075 2232
-4577 -9072
-4482 -6029
8463 -1196
7884 -316
-9376 1920
6846 -8409
2715 -7335
-4977 -4130
9147 1621
-8337 1592
4062 -6829
208 ...

output:

16737

result:

ok 1 number(s): "16737"

Test #8:

score: 0
Accepted
time: 850ms
memory: 4692kb

input:

500
9007 265
2201 5042
5284 -119
5263 2146
9479 -2911
-6239 -4536
2430 978
5311 9052
3692 -754
-2856 -7654
3911 -2955
-4557 6411
-8410 5578
-1429 -8277
-4974 -6226
7160 -2990
-1285 7944
-7144 -6104
-632 -5051
-5904 -3302
-2994 6223
-4918 -773
-2706 -5848
8741 4050
-4544 -3399
-3329 5833
9436 6073
91...

output:

78511

result:

ok 1 number(s): "78511"

Test #9:

score: 0
Accepted
time: 528ms
memory: 4640kb

input:

500
3986 -2058
8393 -5560
-9323 -8268
-7531 8178
-8691 8818
-9752 -1098
8298 -9389
5224 -3089
-5027 2759
-7845 -4577
-7195 6292
8610 4357
-3948 9888
-6300 8917
-7351 2477
1514 -7484
-8936 -5060
-9687 -2927
4009 1765
7666 -4956
1790 -8694
6446 2739
6425 3415
4940 -7749
-2186 1776
3011 -1438
7967 -330...

output:

16065

result:

ok 1 number(s): "16065"

Test #10:

score: 0
Accepted
time: 631ms
memory: 4584kb

input:

500
-374 -6853
8340 3978
2984 9235
7388 7881
9251 -114
9415 -4001
-4986 -9491
4528 -6929
-6788 -3585
4280 -9908
-762 242
2141 -6162
-6597 -1198
-7204 -9704
9557 3683
-2219 -2905
5487 -254
8407 -9416
-2740 -3414
4907 -7751
2333 -1087
-7493 -989
1742 4989
2200 -5320
2136 5551
8421 -4805
-2601 3272
332...

output:

44326

result:

ok 1 number(s): "44326"

Test #11:

score: 0
Accepted
time: 472ms
memory: 4532kb

input:

500
593 4401
-8062 3551
1693 -5367
1067 3359
9605 3156
-406 9613
7086 -4924
-604 -6096
-8304 4829
3056 108
-1251 -8599
-6915 -9995
-1362 -9650
-2693 3354
7446 -7474
-8427 8752
2577 9247
-7860 -8455
-4310 8633
3811 2165
6056 -1335
2385 1666
6845 5528
1344 -7649
9146 8372
-7986 -9293
6077 -4673
1922 4...

output:

6406

result:

ok 1 number(s): "6406"

Test #12:

score: 0
Accepted
time: 357ms
memory: 4616kb

input:

500
3099 -3613
-1110 -8776
-931 -8597
1801 -5174
1445 -5583
7743 2043
1472 -5625
6639 694
-376 -7771
4728 -1624
410 -6958
1388 -5725
-149 -7532
4549 -1874
-4 -7433
2847 -3912
891 -6365
590 -6606
1967 -5042
841 -6287
6004 -57
1223 -5935
-833 -8406
-245 -7679
2117 -4778
7743 2032
1729 -5281
5351 -903
...

output:

197

result:

ok 1 number(s): "197"

Test #13:

score: 0
Accepted
time: 372ms
memory: 4872kb

input:

500
3885 -2913
1167 -5191
73 -8538
2621 -6999
2629 -4437
4959 -465
5623 1751
2643 -1832
1572 -5699
5553 1666
-356 -7904
4749 1822
2349 -6442
3379 -3102
1872 -5412
4961 662
2083 -5685
2096 -6485
4689 -3385
-152 -8592
4433 -1322
3523 -514
4347 580
2503 -4166
-1955 -9807
5591 2896
1192 -6199
5292 160
1...

output:

451

result:

ok 1 number(s): "451"

Test #14:

score: 0
Accepted
time: 376ms
memory: 4872kb

input:

500
4703 -3537
1504 -3821
-6015 649
4331 -4832
-2506 -5255
-6347 -3940
-4134 -3950
-5031 -323
-1641 617
-6416 -5181
-2286 -1047
-3477 -273
1775 -687
-813 -4349
-3080 -5598
-6060 901
4932 -4387
-4701 -5113
-1337 -838
5338 -2177
-5528 1270
2423 -1917
6564 -4480
-3694 851
-5534 -2471
-7040 -1041
-4287 ...

output:

730

result:

ok 1 number(s): "730"

Test #15:

score: 0
Accepted
time: 428ms
memory: 4880kb

input:

500
7026 -796
4816 4861
1394 -296
3528 2969
-7882 1392
-2804 86
-8313 1917
-3064 2479
-247 328
5800 -2136
-1094 -1286
1714 4399
8420 45
-9768 2140
-4357 3676
4346 513
763 -1562
1316 -123
5566 -2472
5627 1144
4377 -2051
1573 -162
-663 2326
2110 -2341
-2981 1763
2642 4347
8728 -232
-250 212
109 3528
-...

output:

1726

result:

ok 1 number(s): "1726"

Test #16:

score: 0
Accepted
time: 395ms
memory: 4644kb

input:

500
1086 -1637
-3054 -5073
3413 -1260
2652 8263
4541 7480
6877 -2262
6482 -1053
4566 -7032
6441 -1846
-4005 5395
5054 294
1954 -3228
-3558 -7090
-733 3598
-2688 9631
-5591 6213
4930 133
-6289 700
-1281 2957
-1931 -1860
-5175 -215
4871 480
5815 1130
2616 7270
-4469 6242
-1606 -4570
-1527 -1512
714 -5...

output:

1636

result:

ok 1 number(s): "1636"

Test #17:

score: 0
Accepted
time: 399ms
memory: 4576kb

input:

500
-4098 -5374
-273 -4345
-7714 -2543
-402 1781
1181 5600
-649 3470
-1834 -4783
-2827 2132
-3728 7158
-3292 5244
-7017 2471
-4170 -217
-4474 2150
-5548 1110
-5063 622
-5113 -6841
-1441 6356
-788 -8869
-3838 -6330
-4971 -6124
-7171 -2830
-7899 3421
-6812 5019
-2875 -8133
-3935 -6568
-1384 -4839
-463...

output:

1933

result:

ok 1 number(s): "1933"

Test #18:

score: 0
Accepted
time: 539ms
memory: 4648kb

input:

500
5829 -5559
1076 5350
1990 -4981
-2819 -1092
-4399 5522
8764 1647
4772 2032
3146 1776
8143 2299
-223 5894
2371 2677
2740 3811
-3681 6540
-4825 4497
1978 -3706
-2779 740
2883 4579
-4622 5659
7763 -1843
6219 467
5671 6080
191 2107
2030 2805
3747 -2114
1349 -5959
3881 4128
-2357 7747
5407 246
7058 8...

output:

10400

result:

ok 1 number(s): "10400"

Test #19:

score: 0
Accepted
time: 435ms
memory: 4648kb

input:

500
-5173 -1176
-4789 -5208
2087 -1307
2704 -3725
7437 319
-2616 5262
6845 -3304
5133 6452
3848 -5212
-7629 1435
1479 8120
-4794 4679
5907 3805
-6280 4522
8428 2486
-503 -1004
2162 -1654
-3573 -5852
4746 6698
2899 -118
4079 -5989
5219 6150
7610 1938
-7783 6278
-5038 2860
-4036 -3160
3276 -2885
109 -...

output:

10280

result:

ok 1 number(s): "10280"

Test #20:

score: 0
Accepted
time: 988ms
memory: 4620kb

input:

500
8 -5246
694 8347
4118 3545
6792 1200
-3866 -6495
-8630 5051
-6449 -5279
2467 1866
1528 3393
-8591 -1037
1442 3832
5564 -3687
3308 1896
-3160 2854
4810 5992
-2438 3712
4084 5843
2705 -7533
7966 602
1665 3345
3186 6666
-7663 3140
4927 4851
-6383 4284
2883 291
-1034 4380
-182 5228
-5679 -4017
985 2...

output:

427502

result:

ok 1 number(s): "427502"

Test #21:

score: -100
Time Limit Exceeded

input:

500
5790 6369
1448 -2220
-2691 -2098
8076 -1871
-7502 -6611
-286 -634
-5341 8453
-2105 -7513
4099 -4617
3598 -9330
5146 -602
3656 4636
6972 -1194
-5992 2205
-2894 -54
415 -3218
-3409 -36
1710 -6872
-1794 4844
-6866 -3165
-8430 326
7198 4957
2300 -2335
-7551 -4571
-4848 5341
8967 -396
960 7519
-7936 ...

output:


result: