QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564010 | #9262. Yandex Museum | PhantomThreshold# | WA | 0ms | 4212kb | C++20 | 5.5kb | 2024-09-14 18:44:05 | 2024-09-14 18:44:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long db;
const db eps=0;
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;}
db rad(point k1,point k2){return atan2(cross(k1,k2),dot(k1,k2));}
vector<point> ConvexHull(vector<point> A,int flag=1){
int n=(int)A.size();
vector<point> ans(n*2);
sort(A.begin(),A.end());
int now=-1;
for (int i=0;i<(int)A.size();i++){
while (now>0 && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
ans[++now]=A[i];
}
int pre=now;
for (int i=n-2;i>=0;i--){
while (now>pre && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
ans[++now]=A[i];
}
ans.resize(now);
return ans;
}
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;
}
);
map<point,vector<pair<point,int>>> vdict;
vector<point> CH;
{
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){
CH.emplace_back(plist[t]);
CH.emplace_back(plist[t+1]);
vdict[plist[t]].emplace_back(plist[t+1],sign(sum[t]));
vdict[plist[t+1]].emplace_back(plist[t],sign(sum[t])*(-1));
}
}
}
}
if (vdict.empty()){
cout << "nice" << "\n";
return 0;
}
sort(CH.begin(),CH.end());
CH.resize(unique(CH.begin(),CH.end())-CH.begin());
CH=ConvexHull(CH);
// point O=CH[0];
// long double scale=(long double)1.0/10000;
// if (CH.size()>=3){
// int sz=CH.size();
// for (int i=0;i<)
// }
bool flag=0;
point O,P,Q;
for (auto &[X,v]:vdict){
sort(v.begin(),v.end(),
[&](const pair<point,int> &A,const pair<point,int> &B){
return sign(cross(A.first-X,B.first-X))>0;
}
);
vector<int> sum(v.size()+1);
for (int i=0;i<(int)v.size();i++){
sum[i]=v[i].second;
if (i>0) sum[i]+=sum[i-1];
}
int presum=0;
for (int i=1;i<(int)v.size();i++){
presum+=v[i-1].second;
if (presum%3==0) continue;
if (flag==0 || rad(P-O,Q-O)<rad(v[i-1].first-X,v[i].first-X)){
flag=1;
O=X;
P=v[i-1].first;
Q=v[i].first;
}
}
}
point dd=(P-O)+(Q-O);
long double scale=100;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
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: 4212kb
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.992928932 0.992928932
result:
ok Both jury and participant found uncovered points, participant point is (0.992928932, 0.992928932) with cover count 2
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 4212kb
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.007071068 0.007071068
result:
wrong answer Point (0.007071068, 0.007071068) is on the boundary of triangle 0 (zero indexed)