题目描述

数据范围

解法

考虑逐次加入每一条直线。

对于当前已加入的直线集合L，现在要新加入一条直线l。

那么它产生的贡献，与平行线有关。

对于任意三条直线，如果其中任意两条平行，那么将不做贡献。

所以给原直线的斜率排序，然后O(n)逐次加入，就能快速求答案了。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#define ll long long

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="trokuti.in";

const char* fout="trokuti.out";

const int inf=0x7fffffff;

const int maxn=400007,mo=1000000007;

int n,i,j,k;

ll ans;

struct line{

    ll x,y,z;

    bool friend operator ==(const line &a,const line &b){

        return (ll)a.x*b.y==(ll)a.y*b.x;

    }

}a[maxn];

bool cmp(const line &a,const line &b){

    /*int k=1;

    if (b.y<0) k*=-1;

    if (a.y<0) k*=-1;

    return (ll)a.x*abs(b.y)*k<(ll)b.x*abs(a.y);*/

    if (a.y==0 && b.y==0) return false;

    else if (a.y==0) return false;

    else if (b.y==0) return true;

    return a.x*1.0/a.y<b.x*1.0/b.y;

}

void qsort(int l,int r){

    int i=l,j=r;

    line mid=a[(l+r)/2];

    while (i<=j){

        while (cmp(a[i],mid)) i++;

        while (cmp(mid,a[j])) j--;

        if (i<=j){

            swap(a[i],a[j]);

            i++;

            j--;

        }

    }

    if (i<r) qsort(i,r);

    if (l<j) qsort(l,j);

}

ll count(int x){

    return (ll)x*(x-1)/2;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d",&n);

    for (i=1;i<=n;i++){

        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

        //a[i].x+=1000000000;

        //a[i].y+=1000000000;

    }

    //sort(a+1,a+n+1,cmp);

    //for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) if (!cmp(a[i],a[j])) swap(a[i],a[j]);

    qsort(1,n);

    j=0;

    k=0;

    for (i=1;i<=n;i++){

        if (i>1 && a[i]==a[i-1]) j++;

        else k+=(count(j+1))%mo,j=0;

        ans=(ans+count(i-1-j)-k)%mo;

    }

    cout<<ans<<endl;

    return 0;

}

启发

垃圾STL，不判断边界条件，不得不手打QSORT。

【JZOJ4894】【NOIP2016提高A组集训第16场11.15】SJR的直线的相关教程结束。