注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

三角形trokuti  

2016-08-13 10:36:19|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题描述
平面上有N条直线,用方程Aix+Biy+Ci=0表示。这些直线没有三线共点的。现在要你计算出用这些直线可以构造出多少三角形?(答案膜1000000007)
三角形trokuti - 杨鸿飞 - 杨鸿飞的博客
==========================
        首先知道一点,三条斜率不同的直线在没有三线共点情况下可以组成一个三角形,这样就可以把题目转化成只跟斜率有关了。
        但是yhf并不懂怎么斜率,也不知道为什么这道题的直线i的斜率是-Ai/Bi,好像是把Aix+Biy+Ci=0化成y=-Ai/Bix-Ci。
        假如在这个平面内,没有平行线,也就是斜率都不相等,那答案就是C(N,3)。不过题目中是会有平行线的,也就是说可能会选中两条平行线,也有可能选中三条,那运用差集的思想,把它们从总答案中减去。看起来很难,其实你只要知道每种斜率有几个就好了(离散化)。
        但yhf用了一种很麻烦正着做的方法,枚举一种斜率,再从前面(避免重复)找另外两种不一样的斜率,也就是随便找两条的方案,再减去找的是平行线的方案。因为要从前面找,所以要用部分和,好麻烦。也是需要知道每种斜率有几个(离散化)。
        对了,关于比较斜率大小(离散化用),比较a/b与c/b即比较a*d与c*b
===========================
方法一(摘lpq神犇)

# include <iostream>

# include <cstdio>

# include <algorithm>

# include <cstring>



using namespace std;

const int oo=1000000007;

const int maxN=300000+20;

struct data

{


int a,b,c;


}x[maxN];

int n,m,sum[maxN];

bool cmp(data a,data b)

{
return 1LL*a.a*b.b<1LL*b.a*a.b;

} // 按照斜率排序



int main()

{

scanf("%d",&n);

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

scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].c);

sort(x,x+n,cmp);

m=0;

sum[0]=1;

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

if (1LL*x[i].a*x[i-1].b==1LL*x[i-1].a*x[i].b) sum[m]++;

else sum[++m]=1; // 分组

long long ans=1LL*n*(n-1)*(n-2)/6; // 不平行的所有情况

for (int i=0; i<=m; i++)

{

if (sum[i]>1) ans-=1LL*sum[i]*(sum[i]-1)/2*(n-sum[i]); // 两条平行的情况

if (sum[i]>2) ans-=1LL*sum[i]*(sum[i]-1)*(sum[i]-2)/6; // 三条平行的情况

}

printf("%I64d\n",ans%oo);

return 0;

}

yhf

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int M=1000000007;
const int MLn=300010;

struct Txl { int x,y; }a[MLn];

bool cmp(Txl i,Txl j)
{ return 1LL*i.x*j.y < 1LL*j.x*i.y; }

int s[MLn];

long long s1[MLn],s2[MLn];

long long C(int x) { return 1LL*x*(x-1)/2; } //C(x,2)

int main()
{
freopen("trokuti.in","r",stdin);
freopen("trokuti.out","w",stdout);

int n; scanf("%d",&n);

int tttt;

for (int i=0; i<n; i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&tttt);

sort(a+0,a+n,cmp);

s[0]=1;

int nowp=0;

for (int i=1; i<n; i++)
{
if (1LL*a[i-1].x*a[i].y!=1LL*a[i].x*a[i-1].y) nowp++;

s[nowp]++;
}

s1[0]=s[0]; s2[0]=C(s[0]);

long long sum=0;

for (int i=1; i<=nowp; i++)
{
sum=sum+(C(s1[i-1])-s2[i-1])*s[i];

s1[i]=s1[i-1]+s[i]; s2[i]=s2[i-1]+C(s[i]); //s1:前面有几条线;s2:有那两条平行
}

printf("%I64d",sum%M);

return 0;
}


  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018