首页 > 其他 > 详细

codeforces 1284E

时间:2020-01-31 19:12:52      阅读:74      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 技术分享图片

 

 计数每一个点被被其他点组成的四边形完全包含的四边形的个数,给出的点没有三点共线的情况

官方题解如下,说的很清楚,也很有技巧

技术分享图片

 

 代码也是直接参考官方的题解来的

#include<bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fore(i, s, t) for (int i = s; i < (int)t; i++)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pf2(x,y) printf("%d %d\n",x,y)
#define pf(x) printf("%d\n",x)
#define each(x) for(auto it:x)	cout<<it<<endl;
#define pi pair<int,int>

using namespace std;

char inline nc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

template <typename T>
bool rd(T& v){
	static char ch;
	while(ch!=EOF&&!isdigit(ch)) ch=nc();
	if(ch==EOF) return false;
	for(v=0;isdigit(ch);ch=nc())
		v=v*10+ch-‘0‘;
	return true;
}

template <typename T>
void o(T p){
	static int stk[70],tp;
	if(p==0) {
		putchar(‘0‘);return ;
	}
	if(p<0) {
		p=-p;putchar(‘-‘);
	}
	while(p) stk[++tp]=p%10,p/=10;
	while(tp) putchar(stk[tp--]+‘0‘);
}

typedef long long ll;

const int maxn=3e3+5;
const int maxm=4e5+5;
const int inf=1e9;

int n;

pi a[maxn];

ll C(ll n,ll m){
	if(m>n) return 0;
	if(n<0) return 0;
	if(m>n-m) m=n-m;
	ll ans=1;
	for(int i=1;i<=m;i++)
		ans*=n,ans/=i,n--;
	return ans;
}

ll cross(pi a,pi b){
	return 1ll*a.fi*b.se-1ll*b.fi*a.se;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i].fi>>a[i].se;
	ll tot=0;
	for(int i=0;i<n;i++){
		vector<pi> v;
		for(int j=0;j<n;j++)
			if(i!=j) v.push_back({a[j].fi-a[i].fi,a[j].se-a[i].se});
		sort(all(v),[&](pi x,pi y){
			bool b1=x<pi(0,0);
			bool b2=y<pi(0,0);
			if(b1!=b2) return b1<b2;
			return cross(x,y)>0;	
		});
		int j=0;
		for(int i=0;i<v.size();i++){
			while(j<i+v.size()&&cross(v[i],v[j%v.size()])>=0) j++;
			tot+=C(j-i-1,3);
		}
	}
	cout<<C(n,5)*5-tot<<endl;
}
 

  

 

codeforces 1284E

原文:https://www.cnblogs.com/033000-/p/12245881.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!