QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91262#5106. Islands from the Sky_skb_WA 2ms3752kbC++175.2kb2023-03-28 04:54:322023-03-28 04:54:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-28 04:54:34]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3752kb
  • [2023-03-28 04:54:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

struct debug {
#define contPrint { *this << "["; \
        int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
        *this << "]"; return *this;}
 
    ~debug(){cerr << endl;}
    template<class c> debug& operator<<(c x) {cerr << x; return *this;}
    template<class c, class d>
    debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")"; 
        return *this;}
    template<class c> debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};

#define dbg(x) "[" << #x << ": " << x << "]  "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() << 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);

using ld = long double;

const ld PI = acosl(-1.0);
const ld EPS = 1e-12;

struct Point {
    ld x, y, z;
    Point() {}
    Point(ld _x, ld _y) : x(_x), y(_y) {}
    Point(ld _x, ld _y, ld _z) : x(_x), y(_y), z(_z) {}
    bool operator<(const Point& other) const {
        return x + EPS < other.x || (abs(x - other.x) < EPS && y < other.y);
    }
};

struct Line {
    ld a, b, c;
    Point p1, p2;
    ld theta;

    Line() {}
    Line(ld _a, ld _b, ld _c) : a(_a), b(_b), c(_c) {calc_theta();}
    Line(Point _p1, Point _p2) : p1(_p1), p2(_p2) {
        ld del_x = p1.x - p2.x;
        ld del_y = p1.y - p2.y;
        a = del_y;
        b = -del_x;
        c = -p1.x * del_y + p1.y * del_x;

        calc_theta();
    }

    void calc_theta() {
        if(b == 0) {
            theta = PI / 2;
        } else {
            theta = atanl(-a / b);
        }
    }

    Line perpendicular(Point p) {
        ld pa, pb, pc;
        pa = b;
        pb = -a;
        pc = -pa * p.x - pb * p.y;
        return Line(pa, pb, pc);
    }

    vector<Point> getPoints(Point p, ld d) {
        vector<Point> ret;
        ret.push_back(Point(p.x + d * cosl(theta), p.y + d * sinl(theta)));
        ret.push_back(Point(p.x + d * cosl(theta + PI), p.y + d * sinl(theta + PI)));
        return ret;
    }
};

int main() 
{
    // auto it = Line(1, 0, 0).getPoints(Point(0, 0), sqrt(2));
    // Wa() dbg(it[0].x) dbg(it[0].y) dbg(it[1].x) dbg(it[1].y);

    int n, m;
    scanf("%d %d", &n, &m);

    vector<vector<Point>> islands(n);
    for(int i = 0; i < n; i++) {
        int p;
        scanf("%d", &p);
        while(p--) {
            ld x, y;
            scanf("%Lf %Lf", &x, &y);
            islands[i].push_back(Point(x, y));
        }
    }

    vector<pair<Point, Point>> routes(m);
    vector<pair<Line, Line>> p_lines(m);

    for(int i = 0; i < m; i++) {
        ld x, y, z;
        scanf("%Lf %Lf %Lf", &x, &y, &z);
        routes[i].first = Point(x, y, z);

        scanf("%Lf %Lf %Lf", &x, &y, &z);
        routes[i].second = Point(x, y, z);

        p_lines[i].first = Line(routes[i].first, routes[i].second).perpendicular(routes[i].first);
        p_lines[i].second = Line(routes[i].first, routes[i].second).perpendicular(routes[i].second);
    }

    auto get_area = [] (vector<Point> v) {
        ld ret = 0;
        v.push_back(v[0]);
        for(int i = 0; i < (int)v.size()-1; i++) {
            ret += v[i].x * v[i+1].y - v[i].y * v[i+1].x;
        }
        return abs(ret);
    };

    ld lo = 0;
    ld hi = PI / 2;
    int step = 60;
    while(step--) {
        ld mid = (lo + hi) / 2;

        vector<vector<Point>> rect(m);
        vector<ld> area(m);
        for(int i = 0; i < m; i++) {
            vector<Point> v1 = p_lines[i].first.getPoints(routes[i].first, routes[i].first.z * tanl(mid));
            vector<Point> v2 = p_lines[i].second.getPoints(routes[i].second, routes[i].second.z * tanl(mid));
            v1.push_back(v2[0]);
            v1.push_back(v2[1]);
            sort(v1.begin(), v1.end());
            sort(v1.begin() + 1, v1.end(), [&] (Point a, Point b) {
                    ld theta1 = v1[0].x - a.x == 0 ? PI / 2 : atanl((v1[0].y - a.y) / (v1[0].x - a.x));
                    ld theta2 = v1[0].x - b.x == 0 ? PI / 2 : atanl((v1[0].y - b.y) / (v1[0].x - b.x));
                    return theta1 + EPS < theta2;
                });
            area[i] = get_area(v1);
            rect[i] = v1;
        }

        int cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                bool inside = true;
                for(auto p : islands[i]) {
                    ld cur_area = 0;
                    for(int k = 0; k < 4; k++) {
                        vector<Point> temp = {rect[j][k], rect[j][(k+1) % 4], p};
                        cur_area += get_area(temp);
                    }

                    if(cur_area - area[j] > EPS) {
                        inside = false;
                        break;
                    }
                }
                if(inside) {
                    cnt++;
                    break;
                }
            }
        }

        if(cnt >= n) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    if(abs(PI / 2 - hi) < EPS) {
        puts("impossible");
    } else {
        printf("%.9Lf\n", lo * 180 / PI);
    }
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3752kb

input:

1 1
3
-5 0
5 0
0 5
-10 10 10 10 10 10

output:

89.999875762

result:

wrong answer