题目3 : 画线
时间限制:
10000ms
单点时限:
1000ms
内存限制:
256MB
描述
小王最近在开发一种新的游戏引擎,但是最近遇到了性能瓶颈。于是他打算从最基本的画线功能开始分析优化。画线其实就是调用一次drawline命令,根据给出的两端坐标,在屏幕画出对应的线段。但是小王发现,很多的drawline其实可以合并在一起,譬如下图中的线段(2,3)-(4,5)和线段(3,4)-(6,7),其实可以合并为一次drawline命令,直接画出线段(2,3)-(6,7)。当然有些线段是无法合并的,如线段(-3,8)-(1,8)和线段(3,8)-(6,8),就必须调用两次drawline命令。
画线示意图。注意颜色只是用于区分,实际线段都是黑色
给出N条drawline指令以及对应的线段坐标,小王想知道,实际最少用多少次drawline指令就可以画出来。
小王想先从最简单的情况开始分析优化,所以线段只包含四种情况:水平线段,垂直线段以及正反45度的线段。
输入
每个输入数据包含多个测试点。
第一行为测试点的个数 S ≤ 10。之后是 S 个测试点的数据。
每个测试点的第一行为 N(N ≤ 105)。之后是 N 行,每行包含4个整数:x0, y0, x1, y1,表示线段(x0,y0)-(x1,y1),坐标的范围在[-108, 108],保证线段的长度大于0。
输出
对于每个测试点,对应的结果输出一行,表示最少用多少次指令即可完成所有的画线。
2 4 3 8 6 8 -3 8 1 8 2 3 4 5 3 4 6 7 5 1 1 2 2 2 2 3 3 3 3 4 2 4 2 5 1 1 0 100 0样例输出
3 3
#include "stdafx.h" #include <vector> #include <iostream> #include <random> #include <map> #include <string> using namespace std; bool judge(int k,vector<vector<int>> input, int first, int second) { int x1 = input[first][0]; int y1 = input[first][1]; int x2 = input[first][2]; int y2 = input[first][3]; int x3 = input[second][0]; int y3 = input[second][1]; int x4 = input[second][2]; int y4 = input[second][3]; if (k !=99) { if ((x1 <= x3&&x3 <= x2) || (x3 <= x1&&x1 <= x4)) return true; } else { if ((y1 <= y3&&y3 <= y2) || (y3 <= y1 || y1 <= y4)) return true; } return false; } int main() { int s; vector<vector<int>> input; vector<pair<int, int>> p; cin >> s; while (s--) { int n; cin >> n; int count = n; for (int i = 0;i < n;i++) { vector<int > t; int a,b,c,d; cin >> a>>b>>c>>d; t.push_back(a); t.push_back(b); t.push_back(c); t.push_back(d); input.push_back(t); if (a == c) p.push_back(make_pair(99,99)); else { int k = (d - b) / (c - a); int s = b - a*k; p.push_back(make_pair(k,s)); } } map<pair<int, int>, vector<int>> m; for (int i = 0;i < p.size();i++) { if ((m.find(p[i]) == m.end())) { vector<int> v; v.push_back(i); m.insert(make_pair(p[i],v)); } else { m[p[i]].push_back(i); } } for(auto i:m) { vector<int > tmp = i.second; for (int j = 0;j < tmp.size() - 1;j++) { for (int k = j + 1;k < tmp.size();k++) { if (judge(i.first.first, input, tmp[j], tmp[k])) count--; } } } cout << count<<endl; } int aa; cin >> aa; return 0; }