牛客挑战赛37

发表于 分类于

为什么打着打着溜了还能涨rating啊…

链接

A

sb 数学题，输出 $2^{2n-3}$ 即可。

B

随便选几个质数，哈希判断一下就好了。

C

按题意递归即可，注意爆long long。

D

题意

笛卡尔坐标系中 $n$ 个点，求三个点组成的三角形的面积在 $[L,R]$ 范围内的个数。

$n\leq 3000$，不存在重点或三点共线。

题解

整场比赛就这题蛮好的。。。

显然算面积用叉积即可。

枚举每一条线段，判断有多少个点符合条件。

如果其他 $n-2$ 个点和该线段的距离是有序的话，那么就可以二分了。

跟线段扯上关系的显然是极角。考虑从小到大枚举极角。

将点按 $x,y$ 为第一二关键字排序后，枚举线段，这样就可以保证线段从左到右，方向确定。再按极角排序，这样就能保证极角在 $[-\frac{\pi}{2},\frac{\pi}{2})$ 内。

于是按顺序枚举极角，每次用两次二分计算答案。做完这个极角以后，发现相对顺序变了的只有这两个点。因此交换这两个点在序列中的位置即可。

时间复杂度 $O(n^2\log n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <complex>
#include <utility>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
//#include <unordered_set>
//#include <unordered_map>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define com complex<db>
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&(-(x)))
#define bit(x,i) (((x)>>(i))&1)
#define Abs(x) ((x)>0?(x):-(x))
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
inline ll read()
{
	ll x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=3005;

struct point{
	ll x,y;
	friend inline bool operator<(const point &A,const point &B)
	{
		if(A.x!=B.x) return A.x<B.x;
		return A.y<B.y;
	}
	friend inline point operator-(const point &A,const point &B)
	{
		return (point){A.x-B.x,A.y-B.y};
	}
};
inline ll cross(const point &A,const point &B)
{
	return A.x*B.y-B.x*A.y;
}
inline ll area2(const point &A,const point &B,const point &C)
{
	return Abs(cross(A-B,A-C));
}
point p[N];
struct line{
	int i,j; db ang;
	friend inline bool operator<(const line &A,const line &B)
	{
		return A.ang<B.ang;
		//return cross(p[A.j]-p[A.i],p[B.j]-p[B.i])>0;
	}
};

line a[N*N];
int n,m,id[N],pos[N];

ll solve(ll S)
{
	ll sum=0;
	fo(i,1,n) pos[i]=id[i]=i;
	int x,y,l,r,mid,ans;
		fo(i,1,m)
		{
		x=a[i].i, y=a[i].j;
		if(pos[x]>pos[y]) swap(x,y);
		l=1; r=pos[x];
		for(;l+1<r;)
		{
			mid=l+r>>1;
			if(area2(p[x],p[y],p[id[mid]])<=S) r=mid;
			else l=mid;
		}
		if(r>=2&&area2(p[x],p[y],p[id[r-1]])<=S) r--;
		sum+=pos[x]-r;
		l=pos[y]; r=n;
		for(;l+1<r;)
		{
			mid=l+r>>1;
			if(area2(p[x],p[y],p[id[mid]])<=S) l=mid;
			else r=mid;
		}
		if(l<n&&area2(p[x],p[y],p[id[l+1]])<=S) l++;
		sum+=l-pos[y];

		swap(pos[x],pos[y]);
		swap(id[pos[x]],id[pos[y]]);
    }
	return sum;
}
ll L,R;
int main()
{
	n=read(); L=read(); R=read();
	fo(i,1,n) p[i].x=read(),p[i].y=read();
	sort(p+1,p+n+1);
	fo(i,1,n) fo(j,i+1,n)
		a[++m]=(line){i,j,atan2(p[j].y-p[i].y,p[j].x-p[i].x)};
	sort(a+1,a+m+1);
	printf("%lld\n",(solve(R*2)-solve(L*2-1))/3);
	return 0;
}

F

链接