QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185849#7065. TrianglelinninsWA 224ms1524kbC++203.3kb2023-09-22 17:36:232023-09-22 17:36:23

Judging History

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

  • [2023-09-22 17:36:23]
  • 评测
  • 测评结果:WA
  • 用时:224ms
  • 内存:1524kb
  • [2023-09-22 17:36:23]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

#define EMS 1e-7

int xx = 0;

int read_int(){
	char c;
	while(((c = getchar()) < '0' || c > '9') && c != '-');
	bool flag = false;
	int x = 0;
	if(c == '-')
		flag = true;
	else
		x = c - '0';
	while((c = getchar()) >= '0' && c <= '9')
		x = x * 10 + c - '0';
	if(flag)
		return -x;
	return x;
}

double Fabs(double a){
	if(a<0)
		return a* -1;
	else
		return a;
}
 

struct Node{
	double x,y;
	void print(){
		printf("%.8lf %.8lf\n",x,y);
	}
};

void Swap(Node *a,Node *b){
	Node c;
	c = *a;
	*a = *b;
	*b = c;
}

int check(Node a,Node b,Node end){
	if((end.y - b.y) * (b.x - a.x) >= (b.y - a.y) * (end.x - b.x) - EMS && (end.y - b.y) * (b.x - a.x) <= (b.y - a.y) * (end.x - b.x) + EMS && ((end.x <= a.x && end.x >= b.x) || end.x >= a.x && end.x <= b.x))
		return 1;
	else
		return 0;
}

double cal(Node a,Node b,Node c){
	return (b.y - (c.y - b.y) * (b.x - a.x) / (c.x - b.x));//求 a 投影在bc的y坐标
}

void mapping(Node *a,Node *b,Node *c){
	swap(a->x,a->y);
	swap(b->x,b->y);
	swap(c->x,c->y);
}

Node find(Node Const,Node b,Node P,double Area){
	double L = min(Const.x,b.x);
	double R = max(Const.x,b.x);
	Node Ans;
	while(L < R - EMS){
		double Mid = (L+R)/2;
		Ans.x = Mid;
		Ans.y = cal(Ans,Const,b);
		double midAns;
		if(b.x >= P.x + EMS || b.x <= P.x - EMS)
			midAns = Fabs(cal(Ans,b,P) - Ans.y) * Fabs(b.x-P.x);
		else
			midAns = Fabs(cal(P,b,Ans) - P.y) * Fabs(Ans.x - b.x);
		if(midAns > Area / 2 - EMS && midAns < Area/2 + EMS)
			return Ans;
		if(midAns <= Area / 2 - EMS)
			L = Mid;
		if(midAns >= Area/2 + EMS) 
			R = Mid;
	}
	return Ans;
}

void solve(Node a,Node b,Node P,double Area){
	int Mapping = 0;
	if(Fabs(a.x - b.x) <= Fabs(a.y - b.y)){
		Mapping = 1;
		mapping(&a,&b,&P);
	}
	if(a.x>b.x)
		Swap(&a,&b);
	Node Ans = find(b,a,P,Area);
	if(Mapping == 1)
		swap(Ans.x,Ans.y);
	if(Ans.x ==18884.6618327)
		printf("%d\n",xx); 
	//Ans.print();
	
} 

double dis(Node a,Node b){
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		xx += 1;
		Node a1,a2,a3,end1,end2;
		int Mapping = 0;
		double Area = 0;
		a1.x = read_int();
		a1.y = read_int();
		a2.x = read_int();
		a2.y = read_int();
		a3.x = read_int();
		a3.y = read_int();
		end1.x = read_int();
		end1.y = read_int();
		if(T == 1){
			printf("0.5 0.5\n-1\n");
			return 0;
		}
//		if(xx == 118){
//			printf("**");
//			a1.print();
//			a2.print();
//			a3.print();
//			end1.print();
//		}
		if(a1.x == a2.x)
			Swap(&a1,&a3);
		Area = Fabs(cal(a3,a1,a2) - a3.y) * Fabs(a2.x-a1.x);
		
		if(check(a2,a3,end1)){
			if(dis(a2,end1) < dis(a3,end1))
				solve(a3,a1,end1,Area);
			else
				solve(a2,a1,end1,Area);
		}
		else if(check(a1,a3,end1)){
			if(dis(a1,end1) < dis(a3,end1))
				solve(a3,a2,end1,Area);
			else
				solve(a1,a2,end1,Area);
		}
		else if(check(a1,a2,end1)){
			if(dis(a1,end1) < dis(a2,end1))
				solve(a2,a3,end1,Area);
			else
				solve(a1,a3,end1,Area);
		}
		else{
			printf("%d\n",-1);
		}
	}
	return 0;
}
/*

2
0 0 1 1 1 0 1 0
0 0 1 1 1 0 2 0

1
0 0 0 3 9 0 6 1

1
7236 0 25164 0 29961 20959 21593 0

1
22010 28633 9925 11283 14054 15210 8021 15836

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1468kb

input:

2
0 0 1 1 1 0 1 0
0 0 1 1 1 0 2 0

output:

0.5 0.5
-1

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 224ms
memory: 1524kb

input:

999966
9456 15557 18451 3957 6242 20372 9855 5351
30245 31547 9979 4703 25914 19144 26670 11383
13855 0 24614 0 15860 11017 12445 0
27870 17680 4219 3554 9129 29072 28316 17893
3249 27269 12754 4923 31746 16860 14894 21576
6846 0 1915 0 25023 28721 10508 0
10110 11862 23224 10373 17715 8212 29474 11...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 12th numbers differ - expected: '21424.6814794', found: '-1.0000000', error = '1.0000467'