QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185764 | #7065. Triangle | linnins | TL | 0ms | 1620kb | C++20 | 2.8kb | 2023-09-22 16:16:52 | 2023-09-22 16:16:52 |
Judging History
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){
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 1620kb
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 ...