QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#552161 | #9253. Prism Palace | ucup-team4504# | AC ✓ | 25ms | 5912kb | C++14 | 2.8kb | 2024-09-07 20:54:18 | 2024-09-07 20:54:20 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int Mod = 998244353;
inline void uadd(int &a, const int &b){ a += b - Mod; a += (a>>31) & Mod; }
inline int add(int a, const int &b){ a += b - Mod; a += (a>>31) & Mod; return a; }
inline void usub(int &a, const int &b){ a -= b; a += (a>>31) & Mod; }
inline int sub(int a, const int &b){ a -= b, a += (a>>31) & Mod; return a; }
inline void umul(int &a, const int &b){ a = (int)(1ll * a * b % Mod); }
inline int mul(const int &a, const int &b){ return (int)(1ll * a * b % Mod); }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 10010;
int fact[fN], invfact[fN], inv[fN];
void initfact(int n){
fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i - 1], i);
invfact[n] = qpow(fact[n], Mod - 2); for(int i = n; i > 0; --i) invfact[i - 1] = mul(invfact[i], i);
for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i - 1]);
}
inline int binom(int n, int m){ return mul(fact[n], mul(invfact[m], invfact[n - m])); }
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template<typename T> inline void chmax(T &_a, const T &_b){ (_b>_a) ? (_a=_b) : _a; }
template<typename T> inline void chmin(T &_a, const T &_b){ (_b<_a) ? (_a=_b) : _a; }
const double eps = 1e-8;
const double pi = acos(-1);
inline int sign(double x){ return (x > eps ? +1 : (x < -eps ? -1 : 0)); }
struct vec{
int x, y;
vec(int _x = 0, int _y = 0){ x = _x, y = _y; }
};
double getang(vec v){ return atan2(v.y, v.x); }
inline bool operator <(vec lh, vec rh){ return ((lh.x != rh.x) ? (lh.x < rh.x) : (lh.y < rh.y)); } // 比大小,先比 x 后比 y
inline double len(vec v){ return sqrt(1.*v.x*v.x + 1.*v.y*v.y); } // 模长
inline vec operator +(vec lh, vec rh){ return vec(lh.x + rh.x, lh.y + rh.y); } // 向量加
inline vec operator -(vec lh, vec rh){ return vec(lh.x - rh.x, lh.y - rh.y); } // 向量减
inline ll dot(vec lh, vec rh){ return 1ll * lh.x * rh.x + 1ll * lh.y * rh.y; } // 向量点乘
inline ll cross(vec lh, vec rh){ return 1ll * lh.x * rh.y - 1ll * lh.y * rh.x; } // 向量叉乘
int n;
vec v[200200];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
rep(i, n) cin >> v[i].x >> v[i].y;
if(cross(v[1] - v[0], v[2] - v[1]) < 0) reverse(v, v + n);
double ans = 0;
rep(i, n) if(cross(v[(i + 1) % n] - v[i], v[(i + 3) % n] - v[(i + 2) % n]) < 0){
double ang = getang(v[(i + 2) % n] - v[(i + 3) % n]) - getang(v[(i + 1) % n] - v[i]);
while(ang < 0) ang += 2. * pi;
while(ang > 2. * pi) ang -= 2. * pi;
ans += ang / pi;
}
cout << fixed << setprecision(12) << ans << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5584kb
input:
3 0 0 1 0 0 1
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5488kb
input:
4 0 0 0 1 1 1 1 0
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5912kb
input:
4 0 0 0 3 1 2 1 1
output:
0.500000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 19ms
memory: 5860kb
input:
199996 719157942 80035870 719158808 80033199 719160795 80027070 719162868 80020675 719165635 80012139 719166422 80009711 719166927 80008153 719168388 80003645 719168539 80003179 719168806 80002355 719168864 80002176 719169119 80001389 719171067 79995376 719173806 79986921 719175195 79982633 71917686...
output:
0.000077716803
result:
ok found '0.0000777', expected '0.0000777', error '0.0000000'
Test #5:
score: 0
Accepted
time: 25ms
memory: 5732kb
input:
199999 521578765 315995242 521578784 315995230 521585008 315991299 521590377 315987908 521597318 315983524 521606119 315977965 521610976 315974897 521614329 315972779 521622922 315967351 521631939 315961655 521636172 315958981 521638241 315957674 521643115 315954595 521650976 315949629 521656567 315...
output:
0.000096532179
result:
ok found '0.0000965', expected '0.0000965', error '0.0000000'
Test #6:
score: 0
Accepted
time: 23ms
memory: 5632kb
input:
200000 88808852 208512084 88810113 208513562 88812008 208515783 88812543 208516410 88816806 208521406 88824507 208530431 88825624 208531740 88831723 208538887 88834262 208541862 88838287 208546578 88845440 208554959 88848801 208558897 88855564 208566821 88856869 208568350 88862876 208575388 88868324...
output:
0.000074373701
result:
ok found '0.0000744', expected '0.0000744', error '0.0000000'
Test #7:
score: 0
Accepted
time: 17ms
memory: 5668kb
input:
199998 2857588 37580055 2857908 37582176 2857951 37582461 2858026 37582958 2859295 37591366 2859678 37593903 2860879 37601857 2862301 37611272 2862330 37611464 2863054 37616255 2864429 37625353 2865434 37632002 2865585 37633001 2867092 37642971 2867321 37644486 2867870 37648118 2868343 37651247 2868...
output:
0.000067539683
result:
ok found '0.0000675', expected '0.0000675', error '0.0000000'
Test #8:
score: 0
Accepted
time: 24ms
memory: 5808kb
input:
199999 487716180 333296644 487720319 333294576 487721706 333293883 487731571 333288954 487734599 333287441 487742738 333283374 487744419 333282534 487746174 333281657 487748301 333280594 487750462 333279514 487754846 333277323 487759670 333274912 487762097 333273699 487764676 333272410 487772963 333...
output:
0.000070696702
result:
ok found '0.0000707', expected '0.0000707', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed