PS: 去年省賽前做過一遍,這次基本就不用模版做第二次,比較基礎。
#include#include #include #include #include #include using namespace std; const double eps = 1e-10; int n; int dcmp(double x) { if(fabs(x) 0 ? 1 : -1; } struct point { double x, y; point(double x=0, double y=0):x(x),y(y){} }; struct stick { point a, b; }; vector v; point operator - (point A, point B) { return point(A.x-B.x, A.y-B.y); } double Cross(point A, point B) { return A.x*B.y - A.y*B.x; } double Dot(point A, point B) { return A.x*B.x + A.y*B.y; } bool SegInter(point a1, point a2, point b1, point b2) { double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1); double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1); return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0; } bool OnSegment(point p, point a1, point a2) { return dcmp(Cross(a1-p, a2-p))==0 && dcmp(Dot(p-a1, p-a2))<=0; } vector res; int main() { point t1, t2; stick tmp; while(scanf("%d", &n)!= EOF && n) { v.clear(); v.push_back(tmp); for(int i =1; i <= n; i++) { scanf("%lf%lf%lf%lf", &tmp.a.x, &tmp.a.y, &tmp.b.x, &tmp.b.y); v.push_back(tmp); } int i, j; bool first, second, third; res.clear(); for( i = 1; i <= n; i++) { for( j = i+1; j <= n; j++) { first = SegInter(v[i].a, v[i].b, v[j].a, v[j].b); second = OnSegment(v[i].a, v[j].a, v[j].b); third = OnSegment(v[i].b, v[j].a, v[j].b); if(first || second || third) break; } if(j>n) res.push_back(i); } printf("Top sticks: "); if(res.size()==1) { printf("%d.\n", res[0]); continue; } else { int len = res.size(); for(int i = 0; i < len-1; i++) { printf("%d, ", res[i]); } printf("%d.\n", res[len-1]); } } return 0; }