QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185765#7065. TrianglelinninsTL 0ms1600kbC++202.8kb2023-09-22 16:18:052023-09-22 16:18:05

Judging History

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

  • [2023-09-22 16:18:05]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:1600kb
  • [2023-09-22 16:18:05]
  • 提交

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);
	while(T--){
		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(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



*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time Limit Exceeded

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
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
-1
-1
-1
14803.424698 6153.871284
-1
-1
8691.653478 2399.790210
-1
-1
19130.798969 688.693599
...

result: