QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#564008#9262. Yandex MuseumPhantomThreshold#WA 1ms4380kbC++205.5kb2024-09-14 18:43:562024-09-14 18:43:57

Judging History

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

  • [2024-09-14 18:43:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4380kb
  • [2024-09-14 18:43:56]
  • 提交

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=1000;
	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: 1ms
memory: 3676kb

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: 4316kb

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.999292893 0.999292893

result:

ok Both jury and participant found uncovered points, participant point is (0.999292893, 0.999292893) with cover count 2

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 4380kb

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.000707107 0.000707107

result:

wrong answer Point (0.000707107, 0.000707107) is on the boundary of triangle 0 (zero indexed)