QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557009 | #9253. Prism Palace | ucup-team1134 | AC ✓ | 35ms | 6444kb | C++23 | 8.9kb | 2024-09-10 23:44:53 | 2024-09-10 23:44:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
//幾何ライブラリ(整数)
class Point{
public:
ll x,y;
Point(ll x=0,ll y=0):x(x),y(y){}
Point operator + (Point p){return Point(x+p.x,y+p.y);}
Point operator - (Point p){return Point(x-p.x,y-p.y);}
Point operator * (ll a){return Point(a*x,a*y);}
double norm(){return x*x+y*y;}
bool operator < (const Point &p)const{
return x<p.x||(x==p.x&&y<p.y);
}
bool operator == (const Point &p)const{
return x==p.x&&y==p.y;
}
};
typedef Point Vector;
ll norm(Vector a){
return a.x*a.x+a.y*a.y;
}
ll dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y;
}
ll cross(Vector a,Vector b){
return a.x*b.y-a.y*b.x;
}
struct Segment{
Point p1,p2;
};
bool isOrthogonal(Vector a,Vector b){
return dot(a,b)==0;
}
bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){
return isOrthogonal(a1-a2,b1-b2);
}
bool isOrthogonal(Segment s1,Segment s2){
return dot(s1.p2-s1.p1,s2.p2-s2.p1)==0;
}
bool isParallel(Vector a,Vector b){
return cross(a,b)==0;
}
bool isParallel(Point a1,Point a2,Point b1,Point b2){
return isParallel(a1-a2,b1-b2);
}
bool isParallel(Segment s1,Segment s2){
return cross(s1.p2-s1.p1,s2.p2-s2.p1)==0;
}
//p0,p1,p2の順に見たときどうなるか?
static const int counter_clockwise=1;
static const int clockwise=-1;
static const int online_back=2;
static const int online_front=-2;
static const int on_segment=0;
int ccw(Point p0,Point p1,Point p2){
Vector a=p1-p0;
Vector b=p2-p0;
if(cross(a,b)>0) return counter_clockwise;
if(cross(a,b)<0) return clockwise;
if(dot(a,b)<0) return online_back;
if(a.norm()<b.norm()) return online_front;
return on_segment;
}
bool intersect(Point p1,Point p2,Point p3,Point p4){
return(ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}
bool intersect(Segment s1,Segment s2){
return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}
bool overlap(Segment s1,Segment s2){
int a=ccw(s1.p1,s1.p2,s2.p1),b=ccw(s1.p1,s1.p2,s2.p2);
if(a&1||b&1) return 0;
if(a==2){
if(b==-2||(b==0&&!(s2.p2==s1.p1))) return 1;
else return 0;
}
if(a==-2){
if(b==2||(b==0&&!(s2.p2==s1.p2))) return 1;
else return 0;
}
if(a==0){
if(s1.p1==s2.p1){
if(b!=2) return 1;
else return 0;
}
else if(s1.p2==s2.p1){
if(b!=-2) return 1;
else return 0;
}
else return 1;
}
return 0;
}
//s1とs2の共通の線分(長さ0より大きい)があるかどうか
typedef Segment Line;
//ネットの適当を書いたのであってるか全く知りません→あってそう
class Circle{
public:
Point c;
ll r;
Circle(Point c=Point(),ll r=0.0):c(c),r(r){}
};
typedef vector<Point> Polygon;
/*
IN 2
ON 1
OUT 0
*/
int contains(Polygon g,Point p){
int n=int(g.size());
bool x=false;
for(int i=0;i<n;i++){
Point a=g[i]-p,b=g[(i+1)%n]-p;
if(a.y>b.y) swap(a,b);
if(a.y<=0&&0<b.y&&cross(a,b)<0) x=!x;
if(abs(cross(a,b))<=0&&dot(a,b)<=0) return 1;
}
return (x?2:0);
}
//ayasii
Polygon andrewScan(Polygon s,bool ok){
Polygon u,l;
sort(all(s));
if(int(s.size())<3) return s;
int n=int(s.size());
u.push_back(s[0]);
u.push_back(s[1]);
l.push_back(s[n-1]);
l.push_back(s[n-2]);
if(ok){
for(int i=2;i<n;i++){
for(int j=int(u.size());j>=2&&ccw(u[j-2],u[j-1],s[i])==counter_clockwise;j--){
u.pop_back();
}
u.push_back(s[i]);
}
for(int i=int(s.size())-3;i>=0;i--){
for(int j=int(l.size());j>=2&&ccw(l[j-2],l[j-1],s[i])==counter_clockwise;j--){
l.pop_back();
}
l.push_back(s[i]);
}
}
if(!ok){
for(int i=2;i<n;i++){
for(int j=int(u.size());j>=2&&ccw(u[j-2],u[j-1],s[i])!=clockwise;j--){
u.pop_back();
}
u.push_back(s[i]);
}
for(int i=int(s.size())-3;i>=0;i--){
for(int j=int(l.size());j>=2&&ccw(l[j-2],l[j-1],s[i])!=clockwise;j--){
l.pop_back();
}
l.push_back(s[i]);
}
}
reverse(all(l));
for(int i=int(u.size())-2;i>=1;i--) l.push_back(u[i]);
return l;
}//ok==1なら辺の上も含める
ll area(Polygon P){
ll sum=0;
for(int i=0;i<si(P);i++){
sum+=cross(P[i],P[(i+1)%si(P)]);
}
return abs(sum);
}
// 倍
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
pair<Point,Vector> perpendicular_bisector(Point a,Point b){
Point c;
c.x=(a.x+b.x)/2;
c.y=(a.y+b.y)/2;
Vector v=b-c;
swap(v.x,v.y);
v.x*=-1;
Point p=c;
if(v.x==0){
v.y=1;
p.y=0;
}
else if(v.y==0){
v.x=1;
p.x=0;
}
else{
if(v.x<0){
v.x*=-1;
v.y*=-1;
}
ll g=gcd(abs(ll(v.x)),abs(ll(v.y)));
v.x/=g;
v.y/=g;
if(p.x>=0){
ll d=p.x/v.x;
p=p-v*d;
}else{
ll d=abs(p.x)/v.x;
p=p+v*d;
if(p.x<0){
p=p+v;
}
}
}
return mp(p,v);
}
//2倍するなりして整数にしておくこと
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
ll N;cin>>N;
if(N==3){
cout<<1<<endl;
return 0;
}
vector<Point> P(N);
for(int i=0;i<N;i++) cin>>P[i].x>>P[i].y;
double res=0;
for(int i=0;i<N;i++){
Point a=P[i],b=P[(i+1)%N],c=P[(i+2)%N],d=P[(i+3)%N];
double sum=0;
sum+=acos((double)(dot(a-b,c-b))/sqrt(norm(a-b))/sqrt(norm(c-b)));
sum+=acos((double)(dot(b-c,d-c))/sqrt(norm(b-c))/sqrt(norm(d-c)));
if(sum<acos(-1)) res+=acos(-1)-sum;
}
res/=acos(-1);
cout<<fixed<<setprecision(25)<<res<<endl;
return 0;
/*
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
while(1){
ll N=rng()%100+1;
vector<Point> P(N);
for(int i=0;i<N;i++){
ll x=abs(ll(rng()%200))-100,y=abs(ll(rng()%200))-100;
P[i]={x,y};
}
P=andrewScan(P,0);
N=si(P);
/*
P.resize(N);
P[0]={0,0};
P[1]={1,1};
P[2]={1,2};
P[3]={0,3};
N=4;
//if(N>=5) continue;
if(N!=5) continue;
ll s=0,t=0;
vector<double> VV;
for(ll q=0;q<10000;q++){
ll x=abs((ll)(rng()%200000000))-100000000,y=abs((ll)(rng()%200000000))-100000000;
if(x*x+y*y<=100000000LL*100000000){
t++;
vl S(N);
for(int i=0;i<N;i++){
Vector v=P[(i+1)%N]-P[i],vv={x,y};
S[i]=abs(cross(v,vv));
}
sort(all(S));
bool f=false;
for(int bit=0;bit<(1<<N);bit++){
ll sum=0;
for(int i=0;i<N;i++){
if(bit&(1<<i)) sum+=S[i];
}
if(sum%2==0&&binary_search(all(S),sum/2)) f=true;
}
if(f){
s++;
VV.pb(atan2(y,x));
}
}
}
//if(s==t||s==0) continue;
double ss=0;
for(int i=0;i<N;i++){
Point a=P[i],b=P[(i+1)%N],c=P[(i+2)%N],d=P[(i+3)%N];
Vector e=d-c,f=a-b;
Vector O={0,0};
int cc=ccw(e,O,f);
if(cc==counter_clockwise){
ss+=acos((double)(dot(f,e))/sqrt(norm(e))/sqrt(norm(f)));
}
}
ss/=M_PI;
cout<<N<<" "<<s<<" "<<t<<" "<<(double)(s)/t<<" "<<ss<<endl;
continue;
sort(all(VV));
for(auto [a,b]:P) cout<<"("<<a<<","<<b<<")"<<endl;
int i=0;
while(i<si(VV)){
int j=i;
while(j+1<si(VV)&&VV[j+1]-VV[j]<=0.05) j++;
cout<<VV[i]<<" "<<VV[j]<<endl;
i=j+1;
}
//return 0;
}
*/
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
3 0 0 1 0 0 1
output:
1
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
4 0 0 0 1 1 1 1 0
output:
0.0000000000000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4160kb
input:
4 0 0 0 3 1 2 1 1
output:
0.4999999999999999444888488
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 35ms
memory: 6376kb
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.0000777168034902920950007
result:
ok found '0.0000777', expected '0.0000777', error '0.0000000'
Test #5:
score: 0
Accepted
time: 32ms
memory: 6204kb
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.0000965321793526363022874
result:
ok found '0.0000965', expected '0.0000965', error '0.0000000'
Test #6:
score: 0
Accepted
time: 35ms
memory: 6444kb
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.0000743737012955406290391
result:
ok found '0.0000744', expected '0.0000744', error '0.0000000'
Test #7:
score: 0
Accepted
time: 35ms
memory: 6280kb
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.0000675396834444813251065
result:
ok found '0.0000675', expected '0.0000675', error '0.0000000'
Test #8:
score: 0
Accepted
time: 35ms
memory: 6280kb
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.0000706967017867891108895
result:
ok found '0.0000707', expected '0.0000707', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed