C++14(g++5.4) 解法, 执行用时: 2785ms, 内存消耗: 106084K, 提交时间: 2020-02-22 12:13:39

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cassert>
using namespace std;
const int maxn=3010;
int n,cnt,to[maxn],ato[maxn];
long long L,R;
struct point{long long x,y;}po[maxn],now[maxn];
struct line {long long x,y;int id1,id2;}li[maxn*maxn];
inline bool cmp(point aa,point bb)
{
	if (aa.x==bb.x) return aa.y<bb.y;
return aa.x<bb.x;
}
inline bool cmp1(line aa,line bb){return aa.x*bb.y-aa.y*bb.x>0;}
long long A(point a,point b,point c)
{
	long long x1=a.x-b.x,y1=a.y-b.y,x2=c.x-b.x,y2=c.y-b.y;
return abs(x2*y1-x1*y2);
}
long long solve(long long S)
{
	long long ans=0;
	for (int i=1;i<=n;i++) now[i]=po[i],to[i]=i,ato[i]=i;
	for (int i=1;i<=cnt;i++)
	{
		int s=ato[li[i].id1],e=ato[li[i].id2];
		//printf("lalal %d %d %d\n",i,s,e);
		if (s>=e) assert(0);
		int l=1,r=s-1,lc=s;
		while (l<=r)
		{
			int mid=(l+r)>>1;
			if (A(now[to[mid]],now[to[s]],now[to[e]])<=S) {lc=min(lc,mid); r=mid-1;}else l=mid+1;
		}
		ans+=s-lc;
		l=e+1; r=n; lc=e;
		while (l<=r)
		{
			int mid=(l+r)>>1;
			if (A(now[to[s]],now[to[e]],now[to[mid]])<=S) {lc=max(lc,mid); l=mid+1;}else r=mid-1;
		}
		ans+=lc-e;
		swap(to[s],to[e]);
		swap(ato[li[i].id1],ato[li[i].id2]);
		//for (int i=1;i<=n;i++) printf("%d ",to[i]);
		//printf("\n");
		//printf("%d %lld\n",i,ans);
	}
return ans;
}
int main()
{
	scanf("%d%lld%lld",&n,&L,&R);
	for (int i=1;i<=n;i++) scanf("%lld%lld",&po[i].x,&po[i].y);
	sort(po+1,po+n+1,cmp);
	//for (int i=1;i<=n;i++) printf("point%d: %lld %lld\n",i,po[i].x,po[i].y);
	for (int i=1;i<=n;i++)
	 for (int j=i+1;j<=n;j++)
	  li[++cnt]={po[j].x-po[i].x,po[j].y-po[i].y,i,j};
	sort(li+1,li+cnt+1,cmp1);
	//for (int i=1;i<=cnt;i++) 
	//printf("line%d: %lld %lld (%d->%d)\n",i,li[i].x,li[i].y,li[i].id1,li[i].id2);
	printf("%lld\n",(solve(2*R)-solve(2*L-1))/3);
return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3235ms, 内存消耗: 70892K, 提交时间: 2020-03-09 11:49:15

#include <bits/stdc++.h>
using namespace std;
const int N=3e3+7,M=5e6+7;
int n,k,x[N],y[N],a[N],id[N]; long long l,r;
struct node{
    int a,b,id1,id2;
}e[M];
struct note{
    int a,b;
}f[N];
inline bool tmp(note a,note b){
    if(a.a==b.a) return a.b>b.b; return a.a>b.a;
}
inline long long getsum(node a,node b){
	return 1ll*a.a*b.b-1ll*a.b*b.a;
}
inline bool cmp(node a,node b){
	return (getsum(a,b)>0);
//	return atan2(a.b,a.a)<atan2(b.b,b.a);
}
inline long long getans(int a,int b,int c){
    return abs(1ll*(f[a].a-f[c].a)*(f[b].b-f[c].b)-1ll*(f[b].a-f[c].a)*(f[a].b-f[c].b));
}
inline long long solve(long long u){
    if(u<=0) return 0; long long ans=0;
    for(int i=1;i<=n;i++) a[i]=id[i]=i;
    for(int i=1;i<=k;i++){
        int x=e[i].id1,y=e[i].id2; if(a[x]>a[y]) swap(x,y);
        int l=1,r=a[x]-1,p=a[x];
        while(l<=r){
            int d=(l+r)>>1;
            if(getans(id[d],x,y)<=u) p=d,r=d-1; else l=d+1;
        }
        ans=ans+a[x]-p;
        l=a[y]+1,r=n,p=a[y];
        while(l<=r){
            int d=(l+r)>>1;
            if(getans(id[d],x,y)<=u) p=d,l=d+1; else r=d-1;
        }
        ans=ans+p-a[y];
        swap(a[x],a[y]),swap(id[a[x]],id[a[y]]);
    }
    return ans/3;
}
int main(){
    cin>>n>>l>>r,l=l*2-1,r=r*2;
    for(int i=1;i<=n;i++) scanf("%d%d",&f[i].a,&f[i].b); sort(f+1,f+n+1,tmp);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            k++,e[k].a=f[i].a-f[j].a,e[k].b=f[i].b-f[j].b,e[k].id1=i,e[k].id2=j;
    sort(e+1,e+k+1,cmp);
    cout<<solve(r)-solve(l)<<endl;
    return 0;
}