比赛 |
20110414 |
评测结果 |
AAAAAAAAAA |
题目名称 |
数三角形 |
最终得分 |
100 |
用户昵称 |
.Xmz |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-04-14 10:57:05 |
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int maxn=100111;
struct point
{
long long x,y;
}P[maxn],T[maxn];
int n;
long long ans;
void init()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
{
scanf("%lld%lld",&P[i].x,&P[i].y);
}
ans=(long long)n*(long long)(n-1)*(long long)(n-2)/6;
}
bool cha(point &a,point &b)
{
return (a.x*b.y-b.x*a.y<0);
}
void pointsort(int l,int r)
{
if (l>=r) return ;
int mid=(l+r)>>1,nowl=l,nowr=r;
for (int i=l;i<=r;i++)
if (i!=mid)
{
if (cha(P[i],P[mid])) T[nowl++]=P[i];
else T[nowr--]=P[i];
}
T[nowl]=P[mid];
for (int i=l;i<=r;i++) P[i]=T[i];
pointsort(l,nowl-1);
pointsort(nowl+1,r);
}
void solve()
{
pointsort(0,n-1);
int j=1;
for (int i=0;i<n;i++)
{
while (cha(P[i],P[j])) j=(j+1>n-1) ? 0 : j+1;
int t=(j+n-1-i)%n;
ans-=t*(t-1)/2;
}
printf("%lld\n",ans);
}
int main()
{
freopen("tricount.in","r",stdin);
freopen("tricount.out","w",stdout);
init();
solve();
return 0;
}