首页 > 代码库 > POJ2653 Pick-up sticks
POJ2653 Pick-up sticks
PS: 去年省赛前做过一遍,这次基本就不用模版做第二次,比较基础。
#include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; const double eps = 1e-10; int n; int dcmp(double x) { if(fabs(x)<eps) return 0; else return 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<stick> 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<int> 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。