#include<bits/stdc++.h> #define mems(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int mod=1e9+7,N=305; struct vec { ll x,y;int id; vec(ll x=0,ll y=0):x(x),y(y){} bool operator==(const vec&o)const{return x==o.x&&y==o.y;} vec operator+(const vec&o)const{ return vec(x+o.x,y+o.y);} vec operator-(const vec&o)const{ return vec(x-o.x,y-o.y);} ll operator*(const vec&o)const{ return x*o.x+y*o.y;} ll operator^(const vec&o)const{ return x*o.y-y*o.x;} vec operator/(const ll&o)const{ return vec(x/o,y/o);} vec operator*(const ll&o)const{ return vec(x*o,y*o);} void sc(){scanf("%lld%lld",&x,&y);} ll len(){return x*x+y*y;} }a[N],b[N],c[N],s,t; int n,t1,t2,le[N],ri[N]; bool cmp1(vec a,vec b) { return ((a-s)^(b-s))>0; } bool cmp2(vec a,vec b) { return ((a-s)^(b-s))<0; } bool cmp3(vec a,vec b) { return ((a-t)^(b-t))>0; } bool cmp4(vec a,vec b) { return ((a-t)^(b-t))<0; } ll ans,res; bool judge(vec a,vec b,vec c,vec d) { ll t1=(a-b)^(b-c),t2=(a-b)^(b-d); return t1*t2<=0; } bool jiao(vec a,vec b,vec c,vec d)//线段相交 { return judge(a,b,c,d)&&judge(c,d,a,b); } void solve() { t1=t2=0; for(int i=1;i<=n;i++) { if(c[i]==s||c[i]==t) continue; if(((t-s)^(c[i]-s))>0) a[++t1]=c[i],a[t1].id=t1;//线段t-s上的点 else b[++t2]=c[i],b[t2].id=t2;//线段t-s下的点 } ans+=t1*(t1-1)*(t1-2)/6;//线段上的三角形 ans+=t2*(t2-1)*(t2-2)/6;//线段下的三角形 sort(a+1,a+1+t1,cmp1); sort(b+1,b+1+t2,cmp1); //线段左边的三角形 for(int i=1,j=1;i<=t1;i++) { while(j<=t2&&(jiao(s,t,a[i],b[j])||!jiao(s,t,a[i],b[j])&&((a[i]-b[j])^(s-b[j]))<0)) j++; ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2; le[a[i].id]=t2-j+1; } sort(a+1,a+1+t1,cmp4); sort(b+1,b+1+t2,cmp4); //线段右边的三角形 for(int i=1,j=1;i<=t1;i++) { while(j<=t2&&(jiao(s,t,a[i],b[j])||!jiao(s,t,a[i],b[j])&&((a[i]-b[j])^(s-b[j]))>0)) j++; ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2; ri[a[i].id]=t2-j+1; } for(int i=1;i<=t1;i++) ans+=le[i]*ri[i];//包含线段,上一个点下两个点 sort(a+1,a+1+t1,cmp2); sort(b+1,b+1+t2,cmp2); for(int i=1,j=1;i<=t2;i++) { while(j<=t1&&(jiao(s,t,a[j],b[i])||!jiao(s,t,a[j],b[i])&&((a[j]-b[i])^(s-b[i]))<0)) j++; le[b[i].id]=t1-j+1; } sort(a+1,a+1+t1,cmp3); sort(b+1,b+1+t2,cmp3); for(int i=1,j=1;i<=t2;i++) { while(j<=t1&&(jiao(s,t,a[j],b[i])||!jiao(s,t,a[j],b[i])&&((a[j]-b[i])^(s-b[i]))>0)) j++; ri[b[i].id]=t1-j+1; } for(int i=1;i<=t2;i++) ans+=le[i]*ri[i];//包含线段,上两个点下一个点 } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) c[i].sc(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)//枚举线段 { s=c[i];t=c[j]; solve(); } printf("%lld\n",ans); }
全部评论
(1) 回帖