QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563948 | #9262. Yandex Museum | PhantomThreshold# | WA | 0ms | 4076kb | C++20 | 4.3kb | 2024-09-14 17:48:56 | 2024-09-14 17:48:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long db;
const db eps=0;
const db scale=1000000;
int sign(db k){
if (k>eps) return 1;
else if (k<-eps) return -1;
return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){x+k1.x,y+k1.y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
bool operator < (const point &k1) const{
int a=cmp(x,k1.x);
if (a==-1) return 1;
else if (a==1) return 0;
return cmp(y,k1.y)==-1;
}
int operator == (const point &k1) const{
return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;
}
point turn90(){return (point){-y,x};}
int getP(){
return sign(x)==-1 || (sign(x)==0 && sign(y)==-1);
}
point getdel(){
if (!getP()) return (*this);
else return (*this)*(-1);
}
friend ostream& operator << (ostream &os,const point &k1){
os << "(" << k1.x << "," << k1.y << ")";
return os;
}
};
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
int compareangle(point k1,point k2){
int a=cmp(k1.getP(),k2.getP());
if (a!=0) return a;
return sign(cross(k2,k1));
}
const int maxn=100000;
int n;
point a[maxn+50][3];
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
for (int i=1;i<=n;i++){
int x0,y0,x1,y1,x2,y2;
cin >> x0 >> y0 >> x1 >> y1 >> x2 >> y2;
a[i][0].x=x0;
a[i][0].y=y0;
a[i][1].x=x1;
a[i][1].y=y1;
a[i][2].x=x2;
a[i][2].y=y2;
if (sign(cross(a[i][1]-a[i][0],a[i][2]-a[i][0]))<0) swap(a[i][1],a[i][2]);
}
vector<tuple<point,point,int>> vec;
for (int i=1;i<=n;i++){
if ((a[i][1]-a[i][0]).getP())
vec.emplace_back(a[i][1],a[i][0],-1);
else
vec.emplace_back(a[i][0],a[i][1],1);
if ((a[i][2]-a[i][1]).getP())
vec.emplace_back(a[i][2],a[i][1],-1);
else
vec.emplace_back(a[i][1],a[i][2],1);
if ((a[i][0]-a[i][2]).getP())
vec.emplace_back(a[i][0],a[i][2],-1);
else
vec.emplace_back(a[i][2],a[i][0],1);
}
auto cmp1=[&](const tuple<point,point,int> &A,const tuple<point,point,int> &B){
auto [Ax,Ay,Aval]=A;
auto [Bx,By,Bval]=B;
int diff=compareangle(Ay-Ax,By-Bx);
if (diff!=0) return diff;
point dir=(Ay-Ax).turn90();
return cmp(dot(Ax,dir),dot(Bx,dir));
};
sort(vec.begin(),vec.end(),
[&](const tuple<point,point,int> &A,const tuple<point,point,int> &B){
return cmp1(A,B)==-1;
}
);
vector<pair<point,point>> vdir;
{
int sz=(int)vec.size();
for (int i=0,j=0;i<sz;i=j){
for (;j<sz && cmp1(vec[i],vec[j])==0;j++);
map<point,int> dict;
vector<point> plist;
for (int k=i;k<j;k++){
dict[get<0>(vec[k])]=0;
dict[get<1>(vec[k])]=0;
}
// cerr << "i,j : " << i << " " << j << endl;
// for (int k=i;k<j;k++){
// cerr << get<0>(vec[k]) << " " << get<1>(vec[k]) << " " << get<2>(vec[k]) << endl;
// }
int id=0;
for (auto &[x,y]:dict){
y=id++;
plist.emplace_back(x);
}
vector<long long> sum(id+5);
for (int k=i;k<j;k++){
sum[dict[get<0>(vec[k])]]+=get<2>(vec[k]);
sum[dict[get<1>(vec[k])]]-=get<2>(vec[k]);
}
for (int t=1;t<id;t++) sum[t]+=sum[t-1];
for (int t=0;t<id-1;t++){
sum[t]%=3;
if (sum[t]!=0){
vdir.emplace_back(plist[t],plist[t+1]);
}
}
}
}
if (vdir.empty()){
cout << "nice" << "\n";
return 0;
}
sort(vdir.begin(),vdir.end(),
[&](const pair<point,point> &A,const pair<point,point> &B){
if (!(A.first==B.first)) return A.first<B.first;
return sign(cross(A.second-A.first,B.second-B.first))>0;
}
);
point O=vdir[0].first;
point P=vdir[0].second;
point Q=vdir[1].second;
point dd=(P-O)+(Q-O);
long double w=hypot(dd.x,dd.y);
long double ansx=O.x+dd.x/w/scale;
long double ansy=O.y+dd.y/w/scale;
cout << "not nice" << "\n";
cout << fixed << setprecision(9) << ansx << " " << ansy << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3664kb
input:
5 0 0 0 2 1 0 0 0 2 0 0 1 0 0 0 2 2 0 2 0 0 1 0 2 0 2 1 0 2 0
output:
nice
result:
ok Both jury and participant think that everything is covered properly
Test #2:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
5 0 0 1 0 0 1 1 0 2 0 1 1 0 0 0 2 2 0 0 1 0 2 1 1 0 0 2 0 0 2
output:
not nice 0.000000894 0.999999553
result:
ok Both jury and participant found uncovered points, participant point is (0.000000894, 0.999999553) with cover count 2
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 4076kb
input:
5 0 0 5 0 5 5 0 0 0 5 5 5 0 5 5 5 5 0 0 5 0 0 5 0 5 0 2 1 3 4
output:
not nice 0.000000707 0.000000707
result:
wrong answer Point (0.000000707, 0.000000707) is on the boundary of triangle 0 (zero indexed)