百度之星 2015 复赛 1001 （数长方形）

本文主要是介绍百度之星 2015 复赛 1001 （数长方形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2
4
3 0 3 3
4 0 4 3
2 1 5 1
2 2 5 2
4
3 0 3 3
4 0 4 3
2 1 5 1
2 2 -5 2

Case #1:
1
Case #2:
0

直接暴力，每次枚举4条线段，判断是否有4个交点，有的话ans++

#include <iostream>
#include <cstdio>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
using namespace std;
const int SIZE=33119;
typedef struct NODE  
{int x1,x2;int y1,y2;};
NODE a[SIZE];bool check(int i, int j)
{if(a[i].x1 == a[i].x2 && a[j].x1 != a[j].x2){return a[i].x1 >= a[j].x1 && a[i].x1 <= a[j].x2 && a[i].y1 <= a[j].y1 && a[i].y2 >= a[j].y1;}else if( a[i].x1 != a[i].x2 && a[j].x1 == a[j].x2){return a[j].x1 >= a[i].x1 && a[j].x1 <= a[i].x2 && a[j].y1 <= a[i].y1 && a[j].y2 >= a[i].y1;}return false;
}bool solve(int b,int c, int d, int e)
{int w[4] = {b,c,d,e};int num = 0;for(int i = 0; i < 4; i++)for(int j = i+1; j < 4; j++)if(check(w[i],w[j])) num++;return num == 4;
}int main()
{#ifdef xxzfreopen("in.txt","r",stdin);#endif // xxint n,i,j,T;scanf("%d",&T);int Case = 1;while (T--){scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);if(a[i].x1 > a[i].x2) swap(a[i].x1,a[i].x2);if(a[i].y1 > a[i].y2) swap(a[i].y1,a[i].y2);}int ans = 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 l = k+1; l < n; l++)if(solve(i,j,k,l)) ans++;printf("Case #%d:\n",Case++);printf("%d\n",ans);}return 0;
}

这篇关于百度之星 2015 复赛 1001 （数长方形）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！