设为首页 加入收藏

TOP

Codeforces Beta Round #32
2014-11-23 20:00:44 来源: 作者: 【 】 浏览:6
Tags:Codeforces Beta Round #32

时运不济,继续水CF。。。

A:Reconnaissance


枚举


B:Borze

模拟


C:Flea

先算出最多可以多少个,然后 统计一下有多少个位置

LL n , m , s;
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
        // freopen ("output.txt" , "w" , stdout);
    #endif
    cin >> n  >> m >> s;
    LL w = (n - 1) / s;
    LL h = (m - 1) / s;
    LL cnt = (w + 1) * (h + 1);
    LL a = min (s - 1 , (m - 1) % s);
    LL b = min (s - 1 , (n - 1) % s);
    cout << (a + 1) * (b + 1) * cnt << endl;
    return 0;
}

D:Constellation

枚举每个位置,枚举半径,然后排序,输出。。


E:Hide and seek

简单几何

首先判断能否直接看到目标,判断条件是不和墙相交 且 (不和镜子相交或者和镜子平行)

然后再判断能否反射看到,做目标点关于镜子的反射点,然后连接源点和反射点,判断与镜子是否有交点,否则不可达。

然后再判断下入射光线和反射光线是否会和墙相交。

const double eps = 1e-8;
int dcmp (double d) {
    return d < -eps   -1 : d > eps;
}
struct Point {
    double x , y;
    Point () {}
    Point (double _x , double _y):x(_x),y(_y){}
    void input () {
        scanf ("%lf %lf" , &x , &y);
    }
    inline Point operator - (const Point &p) const {
        return Point (x - p.x , y - p.y);
    }
    inline Point operator + (const Point &p) const {
        return Point (x + p.x , y + p.y);
    }
    inline double operator * (const Point &p) const {
        return x * p.y - y * p.x;
    }
    inline double operator / (const Point &p) const {
        return x * p.x + y * p.y;
    }
    inline Point operator * (const double d) const {
        return Point (x * d , y * d);
    }
    inline Point operator / (const double d) const {
        return Point (x / d , y / d);
    }
    inline Point turnLeft () {
        return Point (-y , x);
    }
}s , e;
struct Line {
    Point a , b;
    Line () {}
    Line (Point _a , Point _b):a(_a),b(_b){}
    void input () {
        a.input ();
        b.input ();
    }
    inline double operator * (const Point &p) const {
        return (b - a) * (p - a);
    }
    inline double operator / (const Point &p) const {
        return (p - a) / (p - b);
    }
    inline int SegCrossSeg (const Line &v) {
        int d1 = dcmp ((*this) * v.a);
        int d2 = dcmp ((*this) * v.b);
        int d3 = dcmp (v * a);
        int d4 = dcmp (v * b);
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
        return ((d1 == 0 && dcmp ((*this) / v.a) <= 0)
            || (d2 == 0 && dcmp ((*this) / v.b) <= 0)
            || (d3 == 0 && dcmp (v / a) <= 0)
                || (d4 == 0 && dcmp (v / b) <= 0));
    }
    inline bool parallel (Line v) {
        return !dcmp ((b - a) * (v.b - v.a));
    }
    inline Point CrossPoint (const Line &v) {
        double s1 = v * a , s2 = v * b;
        return (a * s2 - b * s1) / (s2 - s1);
    }
    inline Point PointToLine (const Point &p) {
        return CrossPoint (Line (p , p + (a - b).turnLeft ()));
    }
    inline Point SymPoint (const Point &p) {
        return PointToLine (p) * 2 - p;
    }
}wall , mirror;
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
        // freopen ("output.txt" , "w" , stdout);
    #endif
    s.input ();e.input ();
    wall.input ();mirror.input ();
    if (wall.SegCrossSeg (Line (s , e)) == 0 ) {
        if (mirror.SegCrossSeg (Line (s , e)) == 0 || mirror.parallel (Line (s , e))) {
            puts ("YES");
            return 0;
        }
    }
    Point t = mirror.SymPoint (e);
    if (mirror.SegCrossSeg (Line (s , t)) >= 1) {
        Point p = mirror.CrossPoint (Line (s , t));
        if (wall.SegCrossSeg (Line (s , p)) == 0 && wall.SegCrossSeg (Line (p , e)) == 0) {
            puts ("YES");
            return 0;
        }
    }
    puts ("NO");
    return 0;
}

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇UVA216 Getting in Line 下一篇hdu 4696 反状态压缩+动态规划

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·Python爬虫教程(从 (2025-12-26 16:49:14)
·【全269集】B站最详 (2025-12-26 16:49:11)
·Python爬虫详解:原 (2025-12-26 16:49:09)
·Spring Boot Java: (2025-12-26 16:20:19)
·Spring BootでHello (2025-12-26 16:20:15)