首页 > 代码库 > bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形
bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形
USACO划水中。。。
题目中要求经过原点的三角形数目，但这种三角形没什么明显的特点并不好求，所以可以求不经过原点的三角形数量。
对于一个非法三角形，它离原点最近的那条边连接的两个点所连的两条边一定在这个点与原点连线的一侧。
为了不重的计数，只用极角序最小的点算。
实现的时候可以把原数组复制一遍再用一个指针。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#define ll long longusing namespace std;const int N = 200005;int n;ll ans;struct node{ double x,y,ang; friend bool operator < (const node &aa,const node &bb) { return aa.ang<bb.ang; } friend double operator * (const node &aa,const node &bb) { return aa.x*bb.y-aa.y*bb.x; }}a[N];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y); for(int i=1;i<=n;i++)a[i].ang=atan2(a[i].y,a[i].x); sort(a+1,a+n+1); for(int j=1;j<=n;j++)a[n+j]=a[j]; int t=0,r=1; for(int i=1;i<=n;i++) { while(r<i+n-1&&a[i]*a[r+1]>0)r++,t++; ans+=1LL*t*(t-1)/2; t--; } printf("%lld\n",1LL*n*(n-1)*(n-2)/6-ans); return 0;
bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。