QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#770981 | #1196. Fun Region | Jose_17 | RE | 0ms | 4028kb | C++20 | 9.3kb | 2024-11-22 07:13:38 | 2024-11-22 07:13:39 |
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 = 4e18;
using ld = long double;
const ld eps = 1e-6, inf = numeric_limits<ld>::max(), 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;
}
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){
//lines a1+tv1, a2+tv2
//assuming that they intersect
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){
//line a+tv, segment cd
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();
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<pair<point, point>>, 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[i] && 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());
return {Lprov, 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(le((L[j].se - L[j].fi).cross(L[i].fi - L[j].fi), 0) && le((L[j].se - L[j].fi).cross(L[i].se - 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){
auto 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{
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];
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, point p0){
int n = P.size();
int ini = lower_bound(all(P), p0) - P.begin();
vector<int> res;
vector<point> ans;
vector<bool> fls(n, false);
stack<int> q;
q.push(ini); res.pb(ini);
while(q.size()){
int 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;
int u = L[v][0];
q.push(u);
}
ans = convexHull(ans);
return ans;
}
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);
}
vector<vector<int>> L0(n);
auto vx = P;
sort(all(vx));
for(int i = 0; i < n; i++){
L0[lower_bound(all(vx), P[i]) - vx.begin()].pb(lower_bound(all(vx), P[(i + 1) % n]) - vx.begin());
}
auto u = precFunPolygon(P);
auto v = precFunPolygon1(u.fi, u.se);
//for(auto e : u.se) cout<<e<<" "; cout<<'\n';
vector<vector<point>> Ps;
for(int i = 0; i < u.se.size(); i++){
auto t = funPolygon(v.fi, v.se, u.se[i]);
if(t.size() > 3) Ps.pb(t);
}
sort(all(Ps));
Ps.erase(unique(all(Ps)), Ps.end());
auto ans = area(Ps[0]);
for(auto e : Ps){
// for(auto d : e) cout<<d<<" "; cout<<'\n';
}
if(Ps.size() > 1) ans = 0;
cout<<setprecision(25)<<ans;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4028kb
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: 3860kb
input:
10 145 269 299 271 343 193 183 139 408 181 356 324 176 327 147 404 334 434 102 424
output:
12658.31301913107455803242
result:
ok found '12658.3130191', expected '12658.3130191', error '0.0000000'
Test #3:
score: -100
Runtime Error
input:
6 144 401 297 322 114 282 372 178 197 271 368 305