Foj 2148 二维几何(点是否在三角形内)
2024-09-03 00:17:19
题目大意:给n个坐标(不存在三点共线的点),求能够组成多少个凸四边形。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std; struct Point
{
int x,y;
Point(int x=,int y=):x(x),y(y){}
}p[]; typedef Point Vector; Vector operator - (Vector A, Vector B){ return Vector(A.x-B.x,A.y-B.y);} int AbsCross(Vector A,Vector B){ return fabs(A.x*B.y-A.y*B.x);} Point read_point()
{
Point p1;
scanf("%d %d",&p1.x,&p1.y);
return p1;
} bool fun(int i,int j,int k,int m)
{
int area1,area2,area3,area4,sum;
area1=AbsCross(p[j]-p[i],p[k]-p[i]);
area2=AbsCross(p[j]-p[i],p[m]-p[i]);
area3=AbsCross(p[k]-p[i],p[m]-p[i]);
area4=AbsCross(p[k]-p[j],p[m]-p[j]);
sum=area2+area3+area4;
if(sum!=area1) return true;
return false;
} bool is_ok(int i,int j,int k,int m)
{
if(!fun(i,j,k,m)) return false;
if(!fun(i,j,m,k)) return false;
if(!fun(i,k,m,j)) return false;
if(!fun(j,k,m,i)) return false;
return true;
} int main()
{
int i,j,k,m,n,T,Icase,ans;
scanf("%d",&T);
for(Icase=;Icase<=T;Icase++)
{
ans=;
scanf("%d",&n);
for(i=;i<n;i++) p[i]=read_point();
for(i=;i<n-;i++)
{
for(j=i+;j<n-;j++)
{
for(k=j+;k<n-;k++)
{
for(m=k+;m<n;m++)
{
if(is_ok(i,j,k,m))
ans++;
}
}
}
}
printf("Case %d: %d\n",Icase,ans);
}
return ;
}
最新文章
- C#设计模式-责任链模式
- sqlloader导出数据和导入数据
- 合工大 OJ 1322 窗口
- Lua的require和module小结
- HDU 2614 Beat 深搜DFS
- QStringList不是简单重命名的便利类,而是提供了额外的函数,比如sort和join等等
- UML六种关系
- 阿里云开发之OSS数据迁移
- HDU 1003 Max Sum【动态规划求最大子序列和详解 】
- java.net.UnknownHostException
- 项目从.net core 2.1.0升级到.net core 2.2.4,原有项目出错及解决方案
- 洛谷 P1451 求细胞数量
- codeforce R 491 (div2)
- (后台)java 读取excel 文件 Unable to recognize OLE stream 错误
- 第一章 HTML基本标签
- Java的三种代理模式(Proxy,CGLib)
- 20165313 预备作业3 Linux安装及学习
- JavaWeb中四大域对象的作用范围
- tableView中cell的复用机制
- DEX文件类型和虚拟机(摘抄)