JZOJ 【NOIP2016提高A组集训第16场11.15】SJR的直线

题目

Description

Input

Output

Sample Input

6

0 1 0

-5 3 0

-5 -2 25

0 1 -3

0 1 -2

-4 -5 29

Sample Output

Data Constraint

题解

题意

给出\(n\)个条直线的解析式，问这些直线能组成多少个三角形

题解

发现直接求解不容易求

想到可以先求出最大数量再减去不合法的

最大数量\(C_n^3\)，不合法的有两种

两条平行线+一条不平行的
三条平行线

那么可以求出斜率然后按照斜率排序，求出每种相同斜率的个数\(c[i]\)，和总共斜率的个数\(t\)

答案就是\(C_n^3-\sum_{i=1}^tC_{c[i]}^2*(n-c[i])+C_{c[i]}^3\)

Code

#include<cstdio>

#include<algorithm>

#define mod 1000000007

using namespace std;

long long n,ans,t,c[300001];

struct node

{

	long long x,y,z;

}s[300001];

long long read()

{

	long long res=0,fh=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') fh=-1,ch=getchar();

	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();

	return res*fh;

}

bool cmp(node x,node y)

{

	double pd1=x.y?(double)-x.x/x.y:1e100;

	double pd2=y.y?(double)-y.x/y.y:1e100;

	return pd1<pd2;

}

long long C3(long long x) {return (x*(x-1)*(x-2)/6%mod);}

long long C2(long long x) {return (x*(x-1)/2)%mod;}

int main()

{

	freopen("trokuti.in","r",stdin);

	freopen("trokuti.out","w",stdout);

	n=read();

	ans=C3(n);

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

		s[i].x=read(),s[i].y=read(),s[i].z=read();

	sort(s+1,s+n+1,cmp);

	int i=1,j=1;

	while (i<=n)

	{

		while (j<=n&&s[i].x*s[j].y==s[i].y*s[j].x) ++j;

		c[++t]=j-i;

		i=j;

	}

	for (int i=1;i<=t;++i)

		ans=(ans+mod-(C2(c[i])*(n-c[i])%mod)-C3(c[i])+mod)%mod;

	printf("%lld\n",ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西

JZOJ 【NOIP2016提高A组集训第16场11.15】SJR的直线

JZOJ 【NOIP2016提高A组集训第16场11.15】SJR的直线

题目

Description

Input

Output

Sample Input

Sample Output

Data Constraint

题解

题意

题解

Code

最新文章

热门文章