QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#553030 | #9253. Prism Palace | ucup-team1134# | WA | 30ms | 6204kb | C++23 | 9.4kb | 2024-09-08 05:59:51 | 2024-09-08 05:59:51 |
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];
Vector e=d-c,f=a-b;
Vector O={0,0};
int cc=ccw(e,O,f);
if(cc==counter_clockwise){
res+=acos((double)(dot(f,e))/sqrt(norm(e))/sqrt(norm(f)));
}
}
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;
}
*/
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3472kb
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: 0ms
memory: 3792kb
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: 0ms
memory: 4044kb
input:
4 0 0 0 3 1 2 1 1
output:
0.5000000000000000000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 30ms
memory: 6204kb
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:
199992.0000777134846430271863937
result:
wrong answer 1st numbers differ - expected: '0.0000777', found: '199992.0000777', error = '199992.0000000'