2019 牛客多校第八场 F

2019-08-10 by fffasttime·0评论

求平面上四个点形成三点包围一点的方案数。

极角排序扫过去，共线的情况要分类讨论。

```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
typedef long long db;
```
```
typedef db ll;
```
```
 
```
```
int sgn(db x){
```
```
	if (x<0) return -1;
```
```
	return x>0;
```
```
}
```
```
 
```
```
#define Vec const vec &
```
```
#define Point const point &
```
```
struct vec{
```
```
	db x,y;
```
```
	vec():x(0),y(0){}
```

	vec(db x, db y):x(x),y(y){} //[i] init-list is easier to use in c++1x

	vec(db theta):x(cos(theta)),y(sin(theta)){}

```
 
```
```
	db ang() const{return atan2(y,x);}
```
```
 
```

	vec operator+(Vec v) const{return vec(x+v.x,y+v.y);}

	vec operator-(Vec v) const{return vec(x-v.x,y-v.y);}

	vec operator*(db a) const{return vec(x*a,y*a);}

	vec operator/(db a) const{return vec(x/a,y/a);}

```
 
```

	db operator|(Vec v) const{return x*v.x+y*v.y;} //dot

	db operator&(Vec v) const{return x*v.y-y*v.x;} //cross

```
 
```

	bool operator<(Vec v) const{return x==v.x?y<v.y:x<v.x;}

```
	int getid()const{
```
```
		if (x>=0) return y>0?1:4;
```
```
		return y>0?2:3;
```
```
	}
```
```
	void rd(){scanf("%lld%lld",&x,&y);}
```
```
	void prt(){printf("%lld %lld\n",x,y);}
```

	friend ostream& operator<<(ostream &o, Vec v){return o<<v.x<<','<<v.y;}

```
};
```
```
typedef vec point;
```
```
 
```
```
//cmp2 sort by angle without atan2
```
```
// angle range [-pi,pi)
```
```
bool cmp2(Vec a, Vec b){
```
```
	int d1=a.getid(),d2=b.getid();
```
```
	if (d1^d2) return d1<d2;
```
```
	return (a&b)>0;
```
```
}
```
```
const int N=1010;
```
```
point v1[N],p[N];
```
```
bool vis[N];
```
```
 
```
```
int main(){
```
```
	int n0; cin>>n0;
```
```
	for (int i=0;i<n0;i++) p[i].rd();
```
```
	ll ans=0;
```
```
	for (int i=0;i<n0;i++){
```
```
		ll n=0;
```
```
		ll sum=0;
```

		for (int j=0;j<n0;j++) if (i^j) v1[n++]=p[j]-p[i];

```
		sort(v1,v1+n,cmp2);
```
```
		ll l=0,r=1;
```
```
		v1[n]=v1[0];
```
```
		ll sum2=0;
```
```
		memset(vis,0,sizeof vis);
```
```
		for (;l<n;l++){
```
```
			ll sl,sr;
```
```
			vis[l]=1;
```

			for (sl=l;sl+1<n && (v1[sl+1]&v1[sl])==0 && (v1[sl+1]|v1[sl])>0;sl++) vis[sl]=1;

			for (;r<=sl || (!vis[r%n] && ((v1[l]&v1[r%n])>0 || (v1[l]&v1[r%n])==0 && (v1[l]|v1[r%n])>0));r++);

```
			ll cnt=r-l;
```

			if ((v1[l]&v1[r%n])==0 && (v1[l]|v1[r%n])<0){

				for (sr=r;(v1[(sr+1)%n]&v1[sr%n])==0 && !vis[(sr+1)%n] && (v1[(sr+1)%n]|v1[sr%n]);sr++);

```
				sum+=(sl-l+1)*(sl-l)*(sr-r+1)/2;
```
```
				sum+=(sl-l+1)*(sr-r+1)*(r-sl-1);
```
```
			}
```

			if (r-sl>1)	sum+=(sl-l+1)*(r-sl-1)*(r-sl-2)/2;

```
			sum+=(sl-l+1)*(sl-l)*(r-sl-1)/2;
```
```
			sum+=(sl-l+1)*(sl-l)*(sl-l-1)/6;
```
```
			for (int j=l;j<=sl;j++) vis[j]=0;
```
```
			l=sl;
```
```
		}
```
```
		ans+=n*(n-1)*(n-2)/6-sum+sum2/2;
```
```
	}
```
```
	cout<<ans<<'\n';
```
```
	return 0;
```
```
}
```

发表评论取消回复