QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#778516 | #1196. Fun Region | Jose_17 | WA | 227ms | 4684kb | C++20 | 12.9kb | 2024-11-24 15:02:20 | 2024-11-24 15:02:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// Holi c:
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
const int Inf = 1e9;
const ll mod = 1e9+7;
const ll INF = 1e16;
using ld = long double;
const ld eps = 1e-9, inf = 1e8, pi = acos(-1);
bool geq(ld a, ld b){return a-b >= -eps;}
bool leq(ld a, ld b){return b-a >= -eps;}
bool ge(ld a, ld b){return a-b > eps;}
bool le(ld a, ld b){return b-a > eps;}
bool eq(ld a, ld b){return abs(a-b) <= eps;}
bool neq(ld a, ld b){return abs(a-b) > eps;}
struct point {
ld x, y;
point(): x(0), y(0) {}
point(ld x, ld y): x(x), y(y) {}
point operator+(const point & p) const{return point(x + p.x, y + p.y);}
point operator-(const point & p) const{return point(x - p.x, y - p.y);}
point operator*(const ld & k) const{return point(x * k, y * k);}
point operator/(const ld & k) const{return point(x / k, y / k);}
point operator+=(const point & p){*this = *this + p; return *this;}
point operator-=(const point & p){*this = *this - p; return *this;}
point operator*=(const ld & p){*this = *this * p; return *this;}
point operator/=(const ld & p){*this = *this / p; return *this;}
point rotate(const ld & a) const{return point(x*cos(a) - y*sin(a), x*sin(a) + y*cos(a));}
point perp() const{return point(-y, x);}
ld ang() const {
ld a = atan2l(y, x); a += le(a, 0) ? 2*pi : 0; return a;
}
ld dot(const point & p) const{return x * p.x + y * p.y;}
ld cross(const point & p) const{return x * p.y - y * p.x;}
ld norm() const{return x * x + y * y;}
ld length() const{return sqrtl(x * x + y * y);}
point unit() const{return (*this) / length();}
bool operator==(const point & p) const{return eq(x, p.x) && eq(y, p.y);}
bool operator!=(const point & p) const{return !(*this == p);}
bool operator<(const point & p) const{return le(x, p.x) || (eq(x, p.x) && le(y, p.y));}
bool operator>(const point & p) const{return ge(x, p.x) || (eq(x, p.x) && ge(y, p.y));}
bool half(const point & p) const{return le(p.cross(*this), 0) || (eq(p.cross(*this), 0) && le(p.dot(*this), 0));}
};
istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}
int sgn(ld x){
if(ge(x, 0)) return 1;
if(le(x, 0)) return -1;
return 0;
}
void polarSort(vector<pair<point, int>> & P, const point & o, const point & v){
//sort points in P around o, taking the direction of v as first angle
sort(P.begin(), P.end(), [&](const pair<point, int> & a, const pair<point, int> & b){
return point((a.fi - o).half(v), 0) < point((b.fi - o).half(v), (a.fi - o).cross(b.fi - o));
});
}
bool pointInLine(const point & a, const point & v, const point & p){
return eq((p - a).cross(v), 0);
}
bool pointInSegment(const point & a, const point & b, const point & p){
return pointInLine(a, b - a, p) && leq((a - p).dot(b - p), 0);
}
point intersectLines(const point & a1, const point & v1, const point & a2, const point & v2){
ld det = v1.cross(v2);
return a1 + v1 * ((a2 - a1).cross(v2) / det);
}
int intersectLineSegmentInfo(const point & a, const point & v, const point & c, const point & d){
point v2 = d - c;
ld det = v.cross(v2);
if(eq(det, 0)){
if(eq((c - a).cross(v), 0)){
return -1; // infinity points
} else {
return 0; // no point
}
} else {
return sgn(v.cross(c - a)) != sgn(v.cross(d - a)); // 1: single point, 0: no point
}
}
vector<point> convexHull(vector<point> P){
sort(P.begin(), P.end());
vector<point> L, U;
for(int i = 0; i < P.size(); i++){
while(L.size() >= 2 && leq((L[L.size() - 2] - P[i]).cross(L[L.size() - 1] - P[i]), 0)){
L.pop_back();
}
L.push_back(P[i]);
}
for(int i = P.size() - 1; i >= 0; i--){
while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
U.pop_back();
}
U.push_back(P[i]);
}
L.pop_back();
U.pop_back();
L.insert(L.end(), U.begin(), U.end());
return L;
}
ld area(vector<point> & P){
int n = P.size();
if(n <= 2) return 0;
ld ans = 0;
for(int i = 0; i < n; i++){
ans += P[i].cross(P[(i + 1) % n]);
}
return abs(ans / 2);
}
int intersectSegmentsInfo(const point &a, const point &b, const point &c, const point &d) {
point v1 = b - a, v2 = d - c;
int t = sgn(v1.cross(c - a)), u = sgn(v1.cross(d - a));
if (t == u) {
if (t == 0) {
if (pointInSegment(a, b, c) || pointInSegment(a, b, d) || pointInSegment(c, d, a) || pointInSegment(c, d, b)) {
return -1;
} else {
return 0;
}
} else {
return 0;
}
} else {
return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c));
}
}
pair<vector<vector<int>>, vector<point>> precFunPolygon(vector<point> P) {
int n = P.size();
vector<point> prov;
vector<pair<point, point>> Lprov;
for (int i = 0; i < n; i++) {
if (geq((P[(i + 1) % n] - P[i]).cross(P[(i + 2) % n] - P[i]), 0)) {
prov.pb(P[(i + 1) % n]); prov.pb(P[(i + 2) % n]);
Lprov.pb({P[(i + 1) % n], P[(i + 2) % n]});
} else {
point at(INF, INF), seg;
for (int j = 0; j < n; j++) {
if (j == i || j == ((i + 1) % n) || ((j + 1) % n) == i || ((j + 1) % n) == ((i + 1) % n)) continue;
auto u = intersectLineSegmentInfo(P[i], P[(i + 1) % n] - P[i], P[j], P[(j + 1) % n]);
if (u == 1) {
auto v = intersectLines(P[i], P[(i + 1) % n] - P[i], P[j], P[(j + 1) % n] - P[j]);
if (le((P[i] - v).length(), (P[(i + 1) % n] - v).length())) continue;
if (v == P[(j + 1) % n]) continue;
if (v == P[j] && le((P[(i + 1) % n] - v).length(), (P[(i + 1) % n] - at).length())) {
if (ge((v - P[(i + 1) % n]).cross(P[(j - 1 + n) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j - 1 + n) % n];
if (ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j + 1) % n];
} else if (le((P[(i + 1) % n] - v).length(), (P[(i + 1) % n] - at).length())) {
if (ge((v - P[(i + 1) % n]).cross(P[j] - P[(i + 1) % n]), 0)) at = v, seg = P[j];
if (ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j + 1) % n];
}
}
}
prov.pb(P[(i + 1) % n]); prov.pb(at); prov.pb(seg);
Lprov.pb({P[(i + 1) % n], at}); Lprov.pb({at, seg});
}
}
sort(all(prov));
prov.erase(unique(all(prov)), prov.end());
sort(all(Lprov));
Lprov.erase(unique(all(Lprov)), Lprov.end());
int k = prov.size();
vector<vector<int>> Lf(k);
for(int i = 0; i < Lprov.size(); i++){
int i1 = lower_bound(all(prov), Lprov[i].fi) - prov.begin(), i2 = lower_bound(all(prov), Lprov[i].se) - prov.begin();
Lf[i1].pb(i2);
}
return {Lf, prov};
}
pair<vector<vector<int>>, vector<point>> precFunPolygon1(vector<pair<point, point>> L, vector<point> P){
int n = L.size();
map<point, point> mp;
map<point, vector<point>> mps;
vector<pair<point, point>> Lprov;
vector<point> prov;
point minf(-Inf, -Inf);
for(int i = 0; i < n; i++){
point at = L[i].se;
int l1 = -1;
for(int j = 0; j < n; j++){
if(L[i].fi == L[j].fi || L[i].fi == L[j].se || L[i].se == L[j].fi || L[i].se == L[j].se) continue;
if(intersectSegmentsInfo(L[i].fi, L[i].se, L[j].fi, L[j].se) == 1){
if(leq((L[j].se - L[j].fi).cross(L[i].fi - L[j].fi), 0)) continue;
auto it = intersectLines(L[i].fi, L[i].se - L[i].fi, L[j].fi, L[j].se - L[j].fi);
if(it == at) continue;
if(le((it - L[i].fi).length(), (at - L[i].fi).length())) at = it, l1 = j;
}
}
if(at != L[i].se){
int i1 = lower_bound(all(L), make_pair(L[i].fi, minf)) - L.begin(), i2 = lower_bound(all(L), make_pair(L[i].se, minf)) - L.begin();
if(at != L[i].fi) Lprov.pb({L[i].fi, at});
mps[L[l1].fi].pb(at);
mp[L[i].fi] = at;
prov.pb(at); prov.pb(L[i].fi);
}else{
mp[L[i].fi] = L[i].se;
prov.pb(L[i].fi); prov.pb(L[i].se);
Lprov.pb({L[i].fi, L[i].se});
}
}
for(auto e : mps){
auto at = mp[e.fi];
// cout<<e.fi<<" "<<at<<'\n';
for(auto d : e.se){
Lprov.pb({d, at});
}
}
sort(all(prov));
prov.erase(unique(all(prov)), prov.end());
int k = prov.size();
vector<vector<int>> Lf(k);
for(int i = 0; i < Lprov.size(); i++){
int i1 = lower_bound(all(prov), Lprov[i].fi) - prov.begin(), i2 = lower_bound(all(prov), Lprov[i].se) - prov.begin();
Lf[i1].pb(i2);
}
return {Lf, prov};
}
vector<point> funPolygon(vector<vector<int>> L, vector<point> P, int ini){
int n = P.size(), ant = ini;
int v = L[ini][0];
vector<int> res;
vector<point> ans;
vector<bool> fls(n, false);
stack<int> q;
q.push(v); res.pb(v);
while(q.size()){
v = q.top();
res.pb(v);
q.pop();
if(fls[v]){
bool fl = false;
for(int i = 0; i < res.size(); i++){
if(res[i] == v) fl = true;
if(fl) ans.pb(P[res[i]]);
}
break;
}
fls[v] = true;
if(L[v].size() > 1){
vector<pair<point, int>> aux;
for(int l = 0; l < L[v].size(); l++) aux.pb({P[L[v][l]], L[v][l]});
polarSort(aux, P[v], P[v] - P[ant]);
int u = aux[0].se;
q.push(u);
ant = v;
}else{
int u = L[v][0];
q.push(u);
ant = v;
}
}
ans = convexHull(ans);
return ans;
}
struct plane{
point a, v;
plane(): a(), v(){}
plane(const point& a, const point& v): a(a), v(v){}
point intersect(const plane& p) const{
ld t = (p.a - a).cross(p.v) / v.cross(p.v);
return a + v*t;
}
bool outside(const point& p) const{ // test if point p is strictly outside
return le(v.cross(p - a), 0);
}
bool inside(const point& p) const{ // test if point p is inside or in the boundary
return geq(v.cross(p - a), 0);
}
bool operator<(const plane& p) const{ // sort by angle
auto lhs = make_tuple(v.half({1, 0}), ld(0), v.cross(p.a - a));
auto rhs = make_tuple(p.v.half({1, 0}), v.cross(p.v), ld(0));
return lhs < rhs;
}
bool operator==(const plane& p) const{ // paralell and same directions, not really equal
return eq(v.cross(p.v), 0) && ge(v.dot(p.v), 0);
}
};
vector<point> halfPlaneIntersection(vector<plane> planes){
planes.push_back({{0, -inf}, {1, 0}});
planes.push_back({{inf, 0}, {0, 1}});
planes.push_back({{0, inf}, {-1, 0}});
planes.push_back({{-inf, 0}, {0, -1}});
sort(planes.begin(), planes.end());
planes.erase(unique(planes.begin(), planes.end()), planes.end());
deque<plane> ch;
deque<point> poly;
for(const plane& p : planes){
while(ch.size() >= 2 && p.outside(poly.back())) ch.pop_back(), poly.pop_back();
while(ch.size() >= 2 && p.outside(poly.front())) ch.pop_front(), poly.pop_front();
if(p.v.half({1, 0}) && poly.empty()) return {};
ch.push_back(p);
if(ch.size() >= 2) poly.push_back(ch[ch.size()-2].intersect(ch[ch.size()-1]));
}
while(ch.size() >= 3 && ch.front().outside(poly.back())) ch.pop_back(), poly.pop_back();
while(ch.size() >= 3 && ch.back().outside(poly.front())) ch.pop_front(), poly.pop_front();
poly.push_back(ch.back().intersect(ch.front()));
return vector<point>(poly.begin(), poly.end());
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin>>n;
vector<point> P(n);
for(int i = 0; i < n; i++){
int a, b; cin>>a>>b;
P[i] = point(a, b);
}
auto u = precFunPolygon(P);
for(int i = 0; i < u.se.size(); i++){
// cout<<i<<" -> "<<u.se[i]<<" | ";
}
//cout<<'\n';
for(int i = 0; i < u.fi.size(); i++){
// cout<<u.fi[i].fi<<" "<<u.fi[i].se<<'\n';
}
//return 0;
/*auto v = precFunPolygon1(u.fi, u.se);
for(int i = 0; i < v.se.size(); i++){
//cout<<i<<" -> "<<v.se[i]<<" | ";
}
//cout<<'\n';
for(int i = 0; i < v.fi.size(); i++){
// cout<<i<<" -> "<<v.fi[i][0]<<'\n';
//if(v.fi[i].size() > 1) cout<<v.fi[i][1]<<'\n';
}*/
vector<vector<point>> Ps;
for(int i = 0; i < u.se.size(); i++){
if(u.fi[i].size() > 1) continue;
auto t = funPolygon(u.fi, u.se, i);
if(t.size() > 2) Ps.pb(t);
}
sort(all(Ps));
Ps.erase(unique(all(Ps)), Ps.end());
ld ans = 0;
vector<pair<point, point>> r;
for(int i = 0; i < Ps.size(); i++){
for(int j = 0; j < Ps[i].size(); j++){
r.pb({Ps[i][j], Ps[i][(j + 1) % (int)Ps[i].size()]});
}
}
sort(all(r)); r.erase(unique(all(r)), r.end());
vector<plane> vp;
for(auto e : r) vp.pb(plane(e.fi, e.se - e.fi));
auto k = halfPlaneIntersection(vp);
//for(auto e : k) cout<<e;
ans = area(k);
cout<<setprecision(25)<<ans;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4040kb
input:
4 10 0 20 10 10 30 0 10
output:
300
result:
ok found '300.0000000', expected '300.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
10 145 269 299 271 343 193 183 139 408 181 356 324 176 327 147 404 334 434 102 424
output:
12658.31301913107455980878
result:
ok found '12658.3130191', expected '12658.3130191', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
6 144 401 297 322 114 282 372 178 197 271 368 305
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: -100
Wrong Answer
time: 227ms
memory: 4684kb
input:
2000 9274 7020 6000 7020 6000 7030 8801 7030 8801 7040 6000 7040 6000 7050 6517 7050 6517 7060 6000 7060 6000 7070 6182 7070 6182 7080 6000 7080 6000 7090 9928 7090 9928 7100 6000 7100 6000 7110 8928 7110 8928 7120 6000 7120 6000 7130 7778 7130 7778 7140 6000 7140 6000 7150 8627 7150 8627 7160 6000 ...
output:
20000000
result:
wrong answer 1st numbers differ - expected: '80000.0000000', found: '20000000.0000000', error = '249.0000000'