QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91262 | #5106. Islands from the Sky | _skb_ | WA | 2ms | 3752kb | C++17 | 5.2kb | 2023-03-28 04:54:32 | 2023-03-28 04:54:34 |
Judging History
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);
}
}
Details
Tip: Click on the bar to expand more detailed information
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