QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185858 | #7065. Triangle | linnins | WA | 184ms | 1592kb | C++20 | 3.4kb | 2023-09-22 17:47:29 | 2023-09-22 17:47:30 |
Judging History
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 and Ans.x <= 18889)
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
1
9456 15557 18451 3957 6242 20372 9855 5351
1
30245 31547 9979 4703 25914 19144 26670 11383
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 1592kb
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: 184ms
memory: 1560kb
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:
d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** d** 0.5 0.5 -1
result:
wrong output format Expected double, but "d**" found