几何带师

C++14(g++5.4) 解法, 执行用时: 146ms, 内存消耗: 10580K, 提交时间: 2020-03-27 23:04:59

#include<bits/stdc++.h>
using namespace std;
struct P{
    double x,y;
    double operator *(const P &a)const{
        return x*a.y-y*a.x;
    }
    P operator -(const P &a)const{
       return P({x-a.x,y-a.y});
    }
}A[100010],B[100010],C[100010],a,b;
 
struct Q{
    P a,b;
    int v;
};
int cmp1(Q a,Q b){
    return a.a*b.a>0;
}
int cmp2(Q a,Q b){
    return a.b*b.b>0;
}
vector<Q>ll,rr;
 
 
long long ans=0;
int T[100010];
int lb(int x){
    return x&-x;
}
void add(int x,int v){
    for(;x<=1e5;x+=lb(x)) T[x]+=v;
}
int sum(int x){
    int sum=0;
    for(;x;x-=lb(x)) sum+=T[x];
    return sum;
}
void cal(){
    int i;
    memset(T,0,sizeof(T));
    sort(ll.begin(),ll.end(),cmp1);
    for(i=0;i<ll.size();i++) ll[i].v=i+1;
    sort(ll.begin(),ll.end(),cmp2);
    for(i=0;i<ll.size();i++){
        ans+=i-sum(ll[i].v);
        add(ll[i].v,1);
    }
    ll.clear();
}
 
int cmp(P a,P b){
    return a*b>0;
}
vector<P>g;
int main(){
    int i,n,m=0;
    scanf("%d%lf%lf%lf%lf",&n,&a.x,&a.y,&b.x,&b.y);
    P c=b-a,d;
    for(i=1;i<=n;i++){
        scanf("%lf%lf",&A[i].x,&A[i].y);
        d=A[i]-a;
        if(d*c>0){
            B[++m]=A[i]-a;
            C[m]=A[i]-b;
        }
        else g.push_back(A[i]);
    }
    sort(B+1,B+1+m,cmp);
    sort(C+1,C+1+m,cmp);
    for(i=0;i<g.size();i++){
        c=a-g[i];
        d=b-g[i];
        ans+=(upper_bound(C+1,C+1+m,d,cmp)-C-1)-(upper_bound(B+1,B+1+m,c,cmp)-B-1);
    }
    c=b-a;
    for(i=1;i<=n;i++){
        d=A[i]-a;
        if(d*c>0) ll.push_back(Q({A[i]-a,A[i]-b}));
    }
    cal();
    for(i=1;i<=n;i++){
        d=A[i]-a;
        if(d*c<0) ll.push_back(Q({A[i]-a,A[i]-b}));
    }
    cal();
    cout<<ans<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 104ms, 内存消耗: 3148K, 提交时间: 2020-03-28 18:15:07

#include<algorithm>
#include<cstring>
#include<cstdio>
#define mxn 1000010
#define LL long long
#define pii pair<int,int> 
#define fr first
#define sc second
#define mp make_pair
using namespace std;
int n,sl,fh,b[mxn],id[mxn],tr[mxn];
LL ans;
pii A,B,a[mxn],p[mxn];
pii operator -(pii p,pii q) {return mp(p.fr-q.fr,p.sc-q.sc);}
LL operator *(pii p,pii q) {return 1ll*p.fr*q.sc-1ll*p.sc*q.fr;}
int rd()
{
	sl=0;fh=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
	return sl*fh;
}
bool cmp1(int x,int y)
{
	if(b[x]^b[y]) return b[x];
	return (a[x]-A)*(a[y]-A)>0;
}
bool cmp2(int x,int y) {return p[x]<p[y];}
void upd(int i) {for(;i<=n;i+=(i&-i)) tr[i]++;}
int qry(int i) {int res=0; for(;i;i-=(i&-i)) res+=tr[i]; return res;}
int main()
{
	n=rd();A.fr=rd();A.sc=rd();B.fr=rd();B.sc=rd();
	for(int i=1;i<=n;++i) id[i]=i,a[i].fr=rd(),a[i].sc=rd(),b[i]=(A-a[i])*(B-a[i])<0;
	int x;
	sort(id+1,id+n+1,cmp1);
	for(int i=1;i<=n;++i) p[id[i]].fr=i;
	for(int j=1,i=1;i<=n;++i)
	{
		for(x=id[i];(a[x]-A)*(a[id[j%n+1]]-A)>0;j=j%n+1);
		if(b[x]) ans+=(j-i+n)%n;
	}
	swap(A,B);
	sort(id+1,id+n+1,cmp1);
	for(int i=1;i<=n;++i) p[id[i]].sc=i;
	for(int j=1,i=1;i<=n;++i)
	{
		for(x=id[i];(a[x]-A)*(a[id[j%n+1]]-A)>0;j=j%n+1);
		if(b[x]) ans-=(j-i+n)%n;
	}
	swap(A,B);
	if(ans<0) ans=-ans;
	sort(id+1,id+n+1,cmp2);
	for(int j=0,i=1;i<=n;++i)
		if(b[x=id[i]])
		{
			++j;upd(p[x].sc);
			ans+=j-qry(p[x].sc);
		}
	memset(tr+1,0,n<<2);
	for(int j=0,i=1;i<=n;++i)
		if(!b[x=id[i]])
		{
			++j;upd(p[x].sc);
			ans+=j-qry(p[x].sc);
		}
	printf("%lld\n",ans);
	return 0;
}

详情