「BZOJ1914」[Usaco2010 OPen] Triangle Counting 数三角形
Description
在一只大灰狼偷偷潜入Farmer Don的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。想象牧场是一个X，Y平面的网格。她将N只奶牛标记为1…N (1 <= N <= 100,000)，每只奶牛的坐标为X_i,Y_i (-100,000 <= X_i <= 100,000;-100,000 <= Y_i <= 100,000; 1 <= i <=N)。然后她脑海里想象着所有可能由奶牛构成的三角形。如果一个三角形完全包含了原点(0,0)，那么她称这个三角形为“黄金三角形”。原点不会落在任何一对奶牛的连线上。另外，不会有奶牛在原点。给出奶牛的坐标，计算出有多少个“黄金三角形”。顺便解释一下样例，考虑五只牛，坐标分别为(-5,0), (0,2), (11,2), (-11,-6), (11,-5)。下图是由贝西视角所绘出的图示。 
Input
第一行:一个整数: N 第2到第N+1行: 每行两个整数X_i，Y_i，表示每只牛的坐标
Output
* 第一行: 一行包括一个整数，表示“黄金三角形的数量”
Sample Input
5
-5 0
0 2
11 2
-11 -6
11 -5
-5 0
0 2
11 2
-11 -6
11 -5
Sample Output
5
题解
极角排序后对于某个点x，其与原点连线所在直线将平面划分为两部分，若一个部分有t个点，在这t个中任取2个与x显然不构成黄金三角形，答案就是所有三角形去掉非黄金三角形，发现对于每个点只统计某个方向的半平面内的点就能不重不漏
具体实现过程可以用俩指针或者二分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define pi acos(-1.0) #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; ll ans; struct data{ll x,y;double angle;}a[100005]; ll operator*(data a,data b) { return a.x*b.y-a.y*b.x; } bool operator<(data a,data b) { return a.angle<b.angle; } void solve() { int r=1,t=0; for(int i=1;i<=n;i++) { while((r%n+1)!=i&&a[i]*a[r%n+1]>=0)t++,r++; ans+=(ll)t*(t-1)/2; t--; } } int main() { n=read(); for(int i=1;i<=n;i++) { a[i].x=read(),a[i].y=read(); a[i].angle=atan2(a[i].y,a[i].x); } sort(a+1,a+n+1); solve(); printf("%lld\n",(ll)n*(n-1)*(n-2)/6-ans); return 0; } |
计数器 9854117
OI 课件=>
OI 课件=>
[…] hzwer已经说的很好了，在此只能跪烂了 […]
我错了没这种数据QAQ
3
-3 -3
-2 -2
-1 -1
噫