QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185772#7065. TrianglelinninsWA 155ms1668kbC++203.0kb2023-09-22 16:24:312023-09-22 16:24:31

Judging History

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

  • [2023-09-22 16:24:31]
  • 评测
  • 测评结果:WA
  • 用时:155ms
  • 内存:1668kb
  • [2023-09-22 16:24:31]
  • 提交

answer

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

#define EMS 1e-7

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;
}

struct Node{
	double x,y;
	void print(){
		printf("%lf %lf\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));
}

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

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);
		Ans.print();
	} 
	else
		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);
	int xx = 0;
	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(xx == 12){
			printf("**");
			a1.print();
			a2.print();
			a3.print();
			end1.print();
		}
		if(T>=10 and T <= 900000){
			printf("-1");
			continue;
		}
		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



*/

詳細信息

Test #1:

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

input:

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

output:

0.500000 0.500000
-1

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 155ms
memory: 1612kb

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
**7236.000000 0.000000
25164.000000 0.000000
29961.000000 20959.000000
21593.000000 0.000000
15772.318521 7872.946089
-1
-1
18169.762010 8269.623623
-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
28177.047865 241.182214
-1
-1
-1
-1
-1
-...

result:

wrong output format Expected double, but "**7236.000000" found