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

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

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

#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;
}
 

  

最新文章

  1. Sharepoint学习笔记—习题系列--70-576习题解析 -(Q21-Q24)
  2. Swift (if while)
  3. 修改dll版本号处理未能加载“******”,或找不到动态链接库依赖的项
  4. djngo快速实现--使用Bootstrap
  5. stl迭代器原理
  6. 【转载】mysql 四种隔离级别分析
  7. 修改数据库中group_concat的返回结果的长度限制
  8. JQuery this和$(this)的区别及获取$(this)子元素对象的方法
  9. 如何交叉编译开源库--&gt;编译c-ares库从失败到成功的过程[ocean]
  10. poj 1975 Median Weight Bead(传递闭包 Floyd)
  11. FZU 2082 过路费(树链剖分)
  12. 推荐几种PHP实现页面跳转的方法
  13. 会声会影小成果分享(那段青春岁月)——校学习部宣传视频制作&amp;生日祝福
  14. magento 2.2.3 -/.gitignore -/.htaccess 分享
  15. switch and checkbox
  16. 安装MySQL和其他包
  17. webpack 安装,打包使用
  18. Java多线程的悲观锁与乐观锁
  19. java Collections工具类
  20. Python+Android开发

热门文章

  1. 一起了解 .Net Foundation 项目 No.2
  2. Hession矩阵(整理)
  3. 【转】JAVA BIO与NIO、AIO的区别
  4. 1.【Spring Cloud Alibaba】服务发现-Nacos
  5. VFP 的 SPT 起跳 -- 陈纯(BOE数据网络工作室)
  6. docker介绍 架构 安装
  7. 忘记centos的root用户密码怎么办?
  8. 进阶之路 | 奇妙的Animation之旅
  9. asp.net core 3.x Identity
  10. Cassandra 在 360 的实践与改进