本文主要是介绍USACO Spinning Wheels 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题的题目很难懂。。。虽然我自认为英语还不错。。。同样看不懂题目的同学可以看看这里的解释http://www.byvoid.com/blog/usaco-323-spinning-wheels/
同时那里的做法也非常可取，简单明了，对0~359每个角度对每个轮子逐一判断（当然，要具体到每个轮子的每个缺口）。
大神总能写出简单高效的代码http://belbesy.wordpress.com/2012/08/14/usaco-3-2-3-spinning-wheels/。我在慎重考虑自己是不是改行搬砖去。
我的做法和我看到的做法都不一样。用的是整体的角度，先是一个完整的圆，然后逐一减去每个轮子透不过的区域，剩下的就是能透光的区域，如果这个区域和某一个轮子的所有缺口都不重叠，则这一秒没有光通过。
照理说我这种方法相对于每个角度单独考虑会快一些。但写起来麻烦很多，圆上的边是否相交及相交的区域我不知道有没有简洁高效的方法。我的代码中是一个正确的方法，但是根据两条边是否通过360度逐一分情况考虑的，比较繁琐。
/*
ID: thestor1
LANG: C++
TASK: spin
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <algorithm>using namespace std;struct Wedge
{int angle, extent;
};struct Wheel
{int speed;int nWedge;vector<Wedge> wedges;
};bool check(const Wheel* const wheels, int iWheel, const int nWheel, const int intersectAngle, const int intersectExtent)
{if(iWheel >= nWheel){return true;}for(int i = 0; i < wheels[iWheel].nWedge; ++i){int iangle = wheels[iWheel].wedges[i].angle;int iextent = wheels[iWheel].wedges[i].extent;int resAngle; int resExtent;if(iextent == 359){resAngle = intersectAngle;resExtent = intersectExtent;}else if(intersectExtent == 359){resAngle = iangle;resExtent = iextent;}else{int intersectEnd = intersectAngle + intersectExtent;int iend = iangle + iextent;if(intersectEnd >= 360){intersectEnd -= 360;if(iend >= 360){iend -= 360;resAngle = max(iangle, intersectAngle);resExtent = (min(iend, intersectEnd) + 360 - resAngle) % 360;}else{if(intersectEnd < iangle){if(intersectAngle > iend){continue;}resAngle = intersectAngle;resExtent = iend - resAngle;}else{if(check(wheels, iWheel + 1, nWheel, iangle, intersectEnd - iangle)){return true;}if(intersectAngle > iend){continue;}resAngle = intersectAngle;resExtent = iend - resAngle;}}}else{if(iend >= 360){iend -= 360;if(iend < intersectAngle){if(iangle > intersectEnd){continue;}resAngle = iangle;resExtent = intersectEnd - resAngle;}else{if(check(wheels, iWheel + 1, nWheel, intersectAngle, iend - intersectAngle)){return true;}if(iangle > intersectEnd){continue;}resAngle = iangle;resExtent = intersectEnd - resAngle;}}else{if(iangle > intersectEnd || iend < intersectAngle){continue;}resAngle = max(iangle, intersectAngle);resExtent = min(iend, intersectEnd) - resAngle;}}}if(check(wheels, iWheel + 1, nWheel, resAngle, resExtent)){return true;}}return false;
}bool check(Wheel *wheels, const int nWheel)
{return check(wheels, 0, nWheel, 0, 359);
}int main()
{FILE *fin = fopen ("spin.in", "r");FILE *fout = fopen ("spin.out", "w");//freopen("log.txt", "w", stdout);const int nWheel = 5;Wheel wheels[nWheel];for(int i = 0; i < nWheel; ++i){fscanf(fin, "%d", &wheels[i].speed);fscanf(fin, "%d", &wheels[i].nWedge);for(int j = 0; j < wheels[i].nWedge; ++j){Wedge wedge;//int angle, extent;fscanf(fin, "%d%d", &wedge.angle, &wedge.extent);wheels[i].wedges.push_back(wedge);}}int t = 360; for(t = 0; t < 360; ++t){if(check(wheels, nWheel)){break;}for(int i = 0; i < nWheel; ++i){for(int j = 0; j < wheels[i].nWedge; ++j){wheels[i].wedges[j].angle += wheels[i].speed;wheels[i].wedges[j].angle %= 360;}}}if(t < 360){fprintf(fout, "%d\n", t);}else{fprintf(fout, "none\n", t);}return 0;
}这篇关于USACO Spinning Wheels 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
