QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563948#9262. Yandex MuseumPhantomThreshold#WA 0ms4076kbC++204.3kb2024-09-14 17:48:562024-09-14 17:48:57

Judging History

你现在查看的是最新测评结果

  • [2024-09-14 17:48:57]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4076kb
  • [2024-09-14 17:48:56]
  • 提交

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)