题目见 https://codility.com/demo/take-sample-test/epsilon2011/
最近比较忙，偶尔几天才能抽出一个小时左右来想题。而这个题又一直有个小问题，只能拿80分，找了很久没找到，很苦恼。今天突然想到自己构造数据来检查，哈哈，终于一个小时内就找到问题了，修改一提交，100！
由于n条直线最多有O(n^2)的交点，而题目要求的时间复杂度是O(nlgn)，明显暗示就是需要排序…… 所以，首先根据斜率对直线排序，斜率相同的情况下再按截距反向排。从前往后扫描排序好的直线，求出相邻直线的交点，如果该交点比前一个交点的x值还要小，则需要重新计算交点 （这个画个图最清楚了，我很懒就不画了，哈哈），求出的是定义maximum的所有交点。再从后往前扫描排序好的直线，得出定义minimum的所有交点。最后同时对两部分交点扫描，求出每个交点对应在另外一部分的值，计算y值之差后更新全局变量。
说得很乱了，要睡觉了，困。。。
如果有人看到代码不懂的话，可以联系我，不过估计是没有的……
No comments:
Post a Comment