程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2540 && uva 10084 Hotter Colder(半平面交)

poj 2540 && uva 10084 Hotter Colder(半平面交)

編輯:C++入門知識

poj 2540 && uva 10084 Hotter Colder(半平面交)


題目大意:“更冷更熱”是一個游戲:兩個人在一個左下角與右上角左邊為(0,0),(10,10)的正方形房間裡,甲閉上眼睛,乙在房間裡藏一個東西。然後甲猜這個東西在哪裡,第一次必須猜(0,0)。第二次開始每猜一個位置乙都要回答“Hotter”, “Colder”, “Same”。

“Hotter”表示新猜的點比上次猜的點要近,“Colder"表示新猜的點比上次猜的點要遠,“Same"表示兩次猜得一樣近。按順序給出甲每次猜的位置乙的回答。依次輸出每次乙回答後所有可能位置的總面積。


思路:對於兩個點A, B。如果有點P到a的距離小於到b的距離,那麼P一定在A,B中垂線靠近A的那一側,反之則在靠近b的一側。如果P到A,B的距離相等,那麼P一定在A,B的中垂線上。由此可以想象每次回答相當於對答案的多邊形做一次切割,也就是求多邊形與半平面的交。每次切割復雜度O(n)


代碼:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define LL long long


const double eps = 1e-6;
const double pi = acos(-1.0);

int cmp(double x) {
    if(fabs(x) < eps) return 0;
    if(x > 0)return 1;
    return -1;
}

inline double sqr(double x) {
    return x * x;
}



struct point {
    double x, y;
    point(){}
    point(double a, double b): x(a), y(b) {}
    void input(){
        scanf("%lf%lf",&x,&y);
    }

    friend point operator + (const point &a, const point &b) {
        return point(a.x + b.x, a.y + b.y);
    }

    friend point operator - (const point &a, const point &b) {
        return point(a.x - b.x, a.y - b.y);
    }

    friend bool operator == (const point &a, const point &b) {
        return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0;
    }

    friend bool operator < (const point &a, const point& b) {
        return cmp(a.x - b.x) < 0 || cmp(a.x - b.x) == 0 && cmp (a.y - b.y) < 0;
    }

    friend point operator * (const point &a, const double &b) {
        return point(a.x * b, a.y * b);
    }

    friend point operator * (const double &a, const point &b) {
        return point(a * b.x, a * b.y);
    }

    friend point operator / (const point &a, const double &b) {
        return point(a.x / b, a.y / b);
    }
    double norm(){
        return sqrt(sqr(x) + sqr(y));
    }
};

double det(const point &a, const point &b) {
    return a.x * b.y - a.y * b.x;
}

double dot(const point &a, const point &b) {
    return a.x * b.x + a.y * b.y;
}

double dist(const point &a, const point &b) {
    return (a - b).norm();
}

double Angle(point a, point b) {
    if(cmp(dot(a, b) - a.norm() * b.norm()) == 0) return 0;
    if(cmp(dot(a, b) + a.norm() * b.norm()) == 0) return pi;
    return acos(dot(a,b) / a.norm() / b.norm()); 
}

double angle(point p) {
    return atan2(p.y, p.x);
}

point point_rotate(const point &p, double A){
    double tx = p.x, ty = p.y;
    return point(tx * cos(A) - ty * sin(A), tx * sin(A) + ty * cos(A));
}

point point_rotate(const point &p, double sint, double cost) {
    double tx = p.x, ty = p.y;
    return point(tx * cost - ty * sint, tx * sint + ty * cost);
}

struct line {
    point a, b;
    line(){}
    line(point x, point y):a(x),b(y){}
    void input() {
        a.input();
        b.input();
    }
};



void point_pro_line(const point p, const point s, const point t, point &cp) {  
    double r = dot(t - s, p - s) / dot (t - s, t - s);
    cp = s + r * (t - s);
}

bool point_pro_segment(const point p, const point s, const point t, point &cp) {
    if(cmp(dot(p - s, t - s))<0) {
        cp = s;
        return 0;
    }
    if(cmp(dot(p - t, s - t))<0) {
        cp = t;
        return 0;
    }

    double r = dot(t - s, p - s) / dot (t - s, t - s);
    cp = s + r * (t - s);
    return 1;
}

bool point_on_segment(point p, point s, point t) {
    return cmp(det(p - s, t - s))== 0 && cmp(dot(p - s, p - t)) < 0;
}

bool parallel(line a, line b) {
    return !cmp(det(a.a - a.b, b.a - b.b));
}

bool line_cross_line(line a, line b, point &res){
    if(parallel(a, b)) return false;
    double s1 = det(a.a - b.a, b.b - b.a);
    double s2 = det(a.b - b.a, b.b - b.a);
    res = (s1 * a.b - s2 * a.a) / (s1 - s2);
    return true;
}

int segment_cross_segment(const point& a1,const point& a2,const point& b1,const point& b2, point& res) {
    double c1 = det(a2 - a1, b1 - a1);
    double c2 = det(a2 - a1, b2 - a1);
    double c3 = det(b2 - b1, a1 - b1);
    double c4 = det(b2 - b1, a2 - b1);
    if (cmp(c1) * cmp(c2) < 0 && cmp(c3) * cmp(c4) < 0) {
        res.x = (b1.x * c2 - b2.x * c1) / (c2 - c1);
        res.y = (b1.y * c2 - b2.y * c1) / (c2 - c1);
        return 1;
    }

    if(point_on_segment(a1, b1, b2)) {
        res = a1;
        return 2;
    }

    if(point_on_segment(a2, b1, b2)) {
        res = a2;
        return 2;
    }

    if(point_on_segment(b1, a1, a2)) {
        res = b1;
        return 2;
    }

    if(point_on_segment(b2, a1, a2)) {
        res = b2;
        return 2;
    }

    return 0;
}

int segment_cross_segment(const line& l1, const line& l2, point& res) {
    point a1 = l1.a, a2 = l1.b, b1 = l2.a, b2 = l2.b;
    double c1 = det(a2 - a1, b1 - a1);
    double c2 = det(a2 - a1, b2 - a1);
    double c3 = det(b2 - b1, a1 - b1);
    double c4 = det(b2 - b1, a2 - b1);
    if (cmp(c1) * cmp(c2) < 0 && cmp(c3) * cmp(c4) < 0) {
        res.x = (b1.x * c2 - b2.x * c1) / (c2 - c1);
        res.y = (b1.y * c2 - b2.y * c1) / (c2 - c1);
        return 1;
    }

    if(point_on_segment(a1, b1, b2)) {
        res = a1;
        return 2;
    }

    if(point_on_segment(a2, b1, b2)) {
        res = a2;
        return 2;
    }

    if(point_on_segment(b1, a1, a2)) {
        res = b1;
        return 2;
    }

    if(point_on_segment(b2, a1, a2)) {
        res = b2;
        return 2;
    }

    return 0;
}

struct polygon {
    vector P;

    polygon(int size = 0) {
        P.resize(size);
    }
    point& operator [](int index) {
        return P[index];
    }
    int size() {
        return P.size();
    }    

    double area() {
        int n = size();
        double sum = 0;
        for(int i = 0; i < n; i++) sum += det(P[i], P[(i + 1) % n]);
        return sum * 0.5;
    }

};

polygon polygon_cut(polygon& pol, const point& a, const point& b) {
    int n = pol.size();
    point c, d, p;
    polygon ret;
    for(int i = 0; i < n; i++) {
        c = pol[i];
        d = pol[(i + 1) % n];
        if(cmp(det(b - a, c - a)) >= 0) ret.P.push_back(c);
        if(line_cross_line(line(a, b), line(c, d), p)) {
            if(point_on_segment(p, c, d)) ret.P.push_back(p);
        }
    }
    return ret;
}

int main() {
    polygon pol(4);
    pol[0] = point(0, 0);
    pol[1] = point(10, 0);
    pol[2] = point(10, 10);
    pol[3] = point(0, 10);
    point p, q = point(0, 0);
    char str[10];
    bool flag = 0;
    while(scanf("%lf%lf%s", &p.x, &p.y, str) != EOF) {
        point a = (p + q) / 2;
        point b = point_rotate(p - q, pi * 0.5) + a;
        if(str[0] == 'S') flag = 1;
        if(flag) {
            puts("0.00");
            continue;
        }
        if(str[0] == 'C') {
            pol = polygon_cut(pol, a, b);
        }
        else {
            pol = polygon_cut(pol, b, a);
        }
        printf("%.2f\n", fabs(pol.area()));
        q = p;
    }
    return 0;
}


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