程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ2653 Pick-up sticks

POJ2653 Pick-up sticks

編輯:C++入門知識

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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved