QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#244902 | #6620. Linear Fractional Transformation | aries | TL | 0ms | 3796kb | C++14 | 3.2kb | 2023-11-09 16:53:58 | 2023-11-09 16:53:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0,f=1;
char ch=nc();
while(ch<48||ch>57)
{
if(ch=='-')
f=-1;
ch=nc();
}
while(ch>=48&&ch<=57)
x=x*10+ch-48,ch=nc();
return x*f;
}
struct com{
double x,y;
friend com operator +(const com&a,const com&b){
com c;
c.x = a.x + b.x;
c.y = a.y + b.y;
return c;
}
friend com operator -(const com&a,const com&b){
com c;
c.x = a.x - b.x;
c.y = a.y - b.y;
return c;
}
friend com operator *(const com&a,const com&b){
com c;
c.x = a.x*b.x - a.y*b.y;
c.y = a.y*b.x + a.x*b.y;
return c;
}
friend com operator /(const com&a,const com&b){
com c;
c.x = (a.x*b.x + a.y*b.y)/(b.x*b.x + b.y*b.y);
c.y = (-a.x*b.y+a.y*b.x)/(b.x*b.x + b.y*b.y);
return c;
}
friend bool operator ==(const com&a,const com&b){
return fabs(a.x-b.x)<1e-7 && fabs(a.y-b.y)<1e-7;
}
friend com operator -(const com&a){
com c;
c.x = -a.x;c.y = -a.y;
return c;
}
};
com m[10][10];
com fun(int a,int b,int c)
{
return m[1][a]*(m[2][b]*m[3][c] - m[2][c]*m[3][b]) + m[1][b]*(m[2][c]*m[3][a] - m[2][a]*m[3][c])
+ m[1][c]*(m[2][a]*m[3][b] - m[2][b]*m[3][a]);
}
void solve()
{
com z1,z2,z3,w1,w2,w3,z0,w0;
z1.x =read();z1.y = read();w1.x = read();w1.y=read();
z2.x =read();z2.y = read();w2.x = read();w2.y=read();
z3.x =read();z3.y = read();w3.x = read();w3.y=read();
z0.x =read();z0.y = read();
// cin>>z1.x>>z1.y>>w1.x>>w1.y;
// cin>>z2.x>>z2.y>>w2.x>>w2.y;
// cin>>z3.x>>z3.y>>w3.x>>w3.y;
// cin>>z0.x>>z0.y;
com a,b,c,d;
//d=0 c!=0 -> c=1 // (az+b)/z 此时不能有z为0
a = (w1*z1 - w2*z2)/(z1-z2);
b = w1*z1 - a*z1;
if((a*z3 + b)/z3== w3){
w0 = (a*z0+b)/z0;
cout<<w0.x<< " "<<w0.y<<"\n";
return;
}
//az+b/cz+d = w
//az + b - czw = w;
//d!=0 -> d=1
d.x=1;d.y=0;
//c=0
a = (w1-w2)/(z1-z2);
b = w1-a*z1;
if((a*z3 + b) == w3){
w0 = a*z0+b;
cout<<w0.x<< " "<<w0.y<<"\n";
return;
}
//c!=0
m[1][1] = z1;m[1][2] = d;m[1][3] = -z1*w1;m[1][4] = w1;
m[2][1] = z2;m[2][2] = d;m[2][3] = -z2*w2;m[2][4] = w2;
m[3][1] = z3;m[3][2] = d;m[3][3] = -z3*w3;m[3][4] = w3;
com t,ta,tb,tc;
t = fun(1,2,3);
ta = fun(4,2,3);
tb = fun(1,4,3);
tc = fun(1,2,4);
a = ta/t;
b = tb/t;
c = tc/t;
w0 = (a*z0 + b)/(c*z0 + d);
cout<<w0.x<<" "<<w0.y<<"\n";
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
ll T=read();
cin>>T;
cout<<fixed<<setprecision(15);
while(T--){
solve();
}
return 0;
}
/*
2
-1 0 0 -1
0 1 -1 0
1 0 0 1
0 -1
-1 0 -1 0
0 1 0 -1
1 0 1 0
0 -1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
2 -1 0 0 -1 0 1 -1 0 1 0 0 1 0 -1 -1 0 -1 0 0 1 0 -1 1 0 1 0 0 -1
output:
1.000000000000000 0.000000000000000 0.000000000000000 1.000000000000000
result:
ok 4 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
100000 0 0 -1 1 1 1 1 0 1 0 1 -1 -1 0 -1 -1 -1 1 1 -1 1 -1 -1 0 1 0 -1 -1 -1 -1 0 -1 -1 1 -1 -1 0 -1 0 0 1 1 1 0 0 -1 0 0 0 0 -1 -1 1 0 1 1 -1 -1 0 -1 0 1 1 -1 1 0 -1 -1 1 -1 0 1 1 -1 1 0 1 0 0 -1 0 1 -1 -1 1 1 -1 1 0 0 -1 -1 0 1 0 1 1 0 1 1 1 -1 0 1 -1 -1 1 0 -1 0 1 -1 1 0 -1 1 -1 -1 1 0 0 -1 0 1 0...
output:
1.000000000000000 1.666666666666667 -1.000000000000000 1.000000000000000 -1.500000000000000 -0.500000000000000 0.333333333333333 -0.666666666666667 -0.384615384615385 -0.923076923076923 -1.000000000000000 0.000000000000000 -1.500000000000000 0.500000000000000 -0.853658536585366 -0.317073170731707 -1...