QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#798568#8468. Collinear ArrangementsKazemaruTL 0ms4056kbC++171.4kb2024-12-04 15:00:072024-12-04 15:00:13

Judging History

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

  • [2024-12-04 15:00:13]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4056kb
  • [2024-12-04 15:00:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;'0'>ch||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=2e6,V=3e9;
struct xy{int x,y;void rd(){x=read();y=read();}}a[N],o,p,q;
xy operator-(xy a,xy b){return{a.x-b.x,a.y-b.y};}
int chr(xy a,xy b,xy c){a=a-c;b=b-c;return a.x*b.y-a.y*b.x;}
int id(xy a){if(a.x<0)a=o-a;if(a.y<0)a=o-a;int z=abs(__gcd(a.x,a.y));return a.x/z*V+a.y/z;}
unordered_map<int,int>mp;
#define F(x)(chr(p,q,a[x])*P)
inline int clc(int L,int R,int P){int M=(L+R)/2,x=F(M);return L>R?0:x<0?clc(M+1,R,P):x>0?clc(L,M-1,P):1;}
inline int ask(int L,int R,int P){
	int M=(L+R)/2,x=F(M),y=F(M+1),z=0;
	if(L+10>R)f(i,L,R)z+=!F(i);
	else if(x<y&&y<=0)z=ask(M,R,P);
	else if(y<x&&x<=0)z=ask(L,R,M);
	else z=clc(L,M,P)+clc(M+1,R,-P);
	return z;
}
signed main(){
	n=read();m=read();
	f(i,1,n)a[i].rd();
	f(_,1,m){
		if(read()<2){
			p.rd();mp.clear();s=0;
			f(i,1,n)s+=mp[id(p-a[i])]++;
			printf("%lld\n",s);
		}else{
			p.rd();q.rd();
			int P=1,L=1,R=n,M;
			g(i,2,1)if(F(i)>F(i+1))P=-P;
			for(;L<R;F(1)>F(M)?R=M-1:L=M)M=(L+R+1)/2;
			printf("%lld\n",F(1)>0?ask(L+1,n,-P):ask(1,R,P));
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

5 3
0 0
2 0
2 1
1 2
0 2
1 1 1
2 1 1 2 2
1 2 2

output:

1
1
2

result:

ok 3 number(s): "1 1 2"

Test #2:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

1000 1
-139438978 -172098481
-125097652 -169056403
155419484 -28898293
186215972 6874955
240691742 77644763
334255616 236444333
342049790 274206233
342049766 274611851
342049472 275025569
342049298 275242193
342048794 275724449
341967248 297262013
341966000 297569423
341963012 298092233
341960624 29...

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: -100
Time Limit Exceeded

input:

1000 1000
-468718512 100559444
-466285968 100587272
-463035240 100649294
-461326068 100761398
-459427038 100900610
-455064924 101233256
-452216364 101462348
-450021522 101653544
-449086266 101738960
-433665372 103152428
-429959922 103532498
-427457166 103795826
-418983006 104802926
-416443854 105124...

output:


result: