FZU 2148 ——Moon Game 判断凸四边形

题目链接:点击打开链接

题目大意：给你一堆的点，然后判断最多能组成多少个凸四边形

解题思路：因为最多有30个点，所以直接暴力搜索就可以了

所学知识点： 如何判断凸四边形，在这种有坐标的情况下当然是用对角线相交来做了

                        如何判断对角线相交呐：如果两条线段相交，则这两条线段必然相互相互跨立，所以用两次叉积都小于等于0来做就可以了

在判断是不是凸四边形的时候还要注意，只要有一对对角线相交就可以，所以还要枚举一下对角线

//能否组成四边形问题
//判断对角线的香蕉情况，当然不是用包凸啊,xixixi
//用叉积判断对角线的相交情况
//如果相交则必然在两侧
#include
#include
#include
using namespace std;class Point
{
public:int x, y;Point():x(0), y(0) {}Point(int xx, int yy): x(xx), y(yy) {}
};
Point p[35];
int n;void init()
{cin >> n;for(int i = 0; i < n; i++)cin >> p[i].x >> p[i].y;
}bool judge1(Point a, Point b, Point c, Point d) //判断两条线段是否相交
{long long m1 = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);long long m2 = (b.x - a.x) * (d.y - a.y) - (d.x - a.x) * (b.y - a.y);long long m3 = (d.x - c.x) * (a.y - c.y) - (a.x - c.x) * (d.y - c.y);long long m4= (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);if(m1*m2 <= 0 && m3 *m4 <= 0) return true;else return false;
}bool judge2(int i, int j, int k) //判断3个点是否在一条直线上
{int x1 = p[i].x, x2 = p[j].x, x3 = p[k].x;int y1 = p[i].y, y2 = p[j].y, y3 = p[k].y;if((y2-y1)*(x3-x2) == (y3-y2)*(x2-x1)) return false;else return true;
}int solve()
{int cnt = 0;for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){for(int k = j+1; k < n; k++){for(int m = k + 1; m < n; m++){
//                    if(judge(i, j, k) == false) continue;
//                    if(judge(i, j, m) == false) continue;
//                    if(judge(i, k, m) == false) continue;
//                    if(judge(j, k, m) == false) continue;
//                    cout << i << " " << j << " " << k  << " " << m << endl;if(judge1(p[i], p[j], p[k], p[m])||inter(p[i], p[m], p[k], p[j]) || inter(p[i], p[k], p[j], p[m]))cnt++;}}}}return cnt;
}int main()
{int T;scanf("%d", &T);for(int i = 1; i <= T; i++){init();int ans = solve();cout << "Case " << i << ": " << ans << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！