QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297072 | #5067. Two Walls | zzuqy | WA | 76ms | 3876kb | C++14 | 5.3kb | 2024-01-03 22:20:32 | 2024-01-03 22:20:32 |
Judging History
answer
#include <bits/stdc++.h>
#define EPS 1e-14
#define double long double
struct Vector {
long long x, y;
inline Vector() {
}
inline Vector(long long x, long long y) {
this->x = x;
this->y = y;
}
inline Vector operator - (const Vector &a)const {
return (Vector) {
x - a.x, y - a.y
};
}
inline Vector operator + (const Vector &a)const {
return (Vector) {
x + a.x, y + a.y
};
}
inline long long operator * (const Vector &a)const {
return x * a.x + y * a.y;
}
inline long long operator ^ (const Vector &a)const {
return x * a.y - y * a.x;
}
inline double dis() {
return std::sqrt(x * x + y * y);
}
inline int operator == (Vector a) {
return a.x == x && a.y == y;
}
};
inline int sign(long long a) {
if (a == 0)
return 0;
return a > 0 ? 1 : -1;
}
inline int in(Vector a, Vector p, Vector q) {
return ((p - a) * (q - a)) < 0;
}
inline int check(Vector a, Vector b, Vector c, Vector d) {
if (!sign((d - c) ^ (b - a))) {
if (in(a, c, d) || in(b, c, d) || in(c, a, b) || in(d, a, b)) {
return 1;
}
return 0;
}
int cc = sign((c - a) ^ (c - b));
int dd = sign((d - a) ^ (d - b));
int aa = sign((a - c) ^ (a - d));
int bb = sign((b - c) ^ (b - d));
return cc != dd && aa != bb;
}
inline double dis(Vector x, Vector a, Vector b) {
double len = (a - b) * (x - b) / std::sqrt((a - b).dis());
return (x - b).dis() - len * len ;
}
bool compare(Vector a,Vector b,Vector c){
if(a.x==0&&a.y==0)return 0;
long long tmp1=a^c;
long long tmp2=a^b;
double tmp3=a.x*(b.y+c.y/c.dis()*b.dis())-a.y*(b.x+c.x/c.dis()*b.dis());
double tmp4=-c.x*(b.y+c.y/c.dis()*b.dis())+c.y*(b.x+c.x/c.dis()*b.dis());
//std::cout<<tmp1<<" "<<tmp2<<std::endl;
//if(tmp1>0&&tmp2>0||tmp1<0&&tmp2<0)c=Vector(0,0)-c;
if(tmp1==0){
if(a.x>0&&b.x>0||a.x<0&&b.x<0||a.y>0&&b.y>0||a.y<0&&b.y<0){
if(tmp2==0&&(a.x>0&&c.x>0||a.x<0&&c.x<0||a.y>0&&c.y>0||a.y<0&&c.y<0))return 0;
return 1;
}
return 0;
}
if(tmp2==0){
if(a.x>0&&c.x>0||a.x<0&&c.x<0||a.y>0&&c.y>0||a.y<0&&c.y<0){
return 0;
}
return 1;
}
if(tmp1<0&&tmp2>0||tmp1>0&&tmp2<0){
if(a.y*(b.y+c.y/c.dis()*b.dis())+a.x*(b.x+c.x/c.dis()*b.dis())<0){
b=Vector(0,0)-b;c=Vector(0,0)-c;
tmp3=a.x*(b.y+c.y/c.dis()*b.dis())-a.y*(b.x+c.x/c.dis()*b.dis());
if(tmp3>0&&tmp1<0||tmp3<0&&tmp1>0)return 1;
return 0;
}
if(tmp3>0&&tmp1>0||tmp3<0&&tmp1<0)return 1;
return 0;
}
else {
if(tmp3>0&&tmp4>0||tmp3<0&&tmp4<0)return 1;
return 0;
}
}
#define base 2147483648
struct bigint{
long long x[8],len;
};
struct bigint newbigint(long long x){
struct bigint tmp;
for(int i=0;i<8;i++)tmp.x[i]=0;
tmp.len=1;tmp.x[0]=x;
while(tmp.x[tmp.len-1]>base){
tmp.x[tmp.len]=tmp.x[tmp.len-1]/base;
tmp.x[tmp.len-1]%=base;tmp.len++;
}
return tmp;
}
struct bigint Multiply(struct bigint a,struct bigint b){
struct bigint ret=newbigint(a.len+b.len);
for(int i=0;i<ret.len;i++)ret.x[i]=0;
for(int i=0;i<a.len;i++){
if(a.x[i]==0)continue;
for(int j=0;j<b.len;j++){
ret.x[i+j]+=a.x[i]*b.x[j];
ret.x[i+j+1]+=ret.x[i+j]/base;
ret.x[i+j]%=base;
}
}
while(ret.len&&ret.x[ret.len-1]==0)ret.len--;//将多余的空位扔掉
return ret;
}
bool Compare(struct bigint a,struct bigint b){
printf("%d %d\n",a.len,b.len);
if(a.len>b.len)return 1;
if(a.len<b.len)return 0;
int flag=1;
for(int i=a.len-1;i>=0;i--){
if(a.x[i]<b.x[i])return 0;
if(a.x[i]>b.x[i])return 1;
}
return 0;
}
bool compare(Vector a,Vector b,Vector an,Vector bn){
if((b-a)*(an-a)<=0&&(b-a)*(bn-b)>=0)return 0;
if((b-a)*(an-a)>=0&&(b-a)*(bn-b)<=0)return 1;
bool flag=1;
if((b-a)*(an-a)<0)flag=0;
long long tmp1=std::max((b-a)*(an-a),-((b-a)*(an-a)));
long long tmp2=std::max((b-a)*(bn-b),-((b-a)*(bn-b)));
struct bigint Num1=newbigint((bn-b)*(bn-b));
struct bigint Numt=newbigint(tmp1);
printf("%d\n",Num1.x[0]);
Num1=Multiply(Num1,Numt);Num1=Multiply(Num1,Numt);
struct bigint Num2=newbigint((an-a)*(an-a));
Numt=newbigint(tmp2);
Num2=Multiply(Num2,Numt);Num2=Multiply(Num2,Numt);
if(Compare(Num1,Num2))return flag;
return !flag;
}
int main() {
int $;
scanf("%d", &$);
while ($--) {
Vector a;
Vector b;
Vector c1;
Vector c2;
Vector d1;
Vector d2;
scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",
&a.x, &a.y, &b.x, &b.y, &c1.x, &c1.y, &c2.x, &c2.y, &d1.x, &d1.y, &d2.x, &d2.y);
if (!check(a, b, c1, c2) && !check(a, b, d1, d2)) {
puts("0");
} else if (c1 == d1 || c2 == d1 || c1 == d2 || c2 == d2) {
puts("1");
} else if (!sign((d2 - d1) ^ (c2 - c1))) {
puts("1");
} else if (!check(c1, c2, d1, d2)) {
puts("1");
} else if (check(a, b, c1, c2) + check(a, b, d1, d2) == 1) {
puts("1");
} else if (!sign((b - a) ^ (c2 - c1)) || !sign((b - a) ^ (d2 - d1))) {
puts("1");
} else {
Vector a0(0, 0), a1(0, 0);
Vector b0(0, 0), b1(0, 0);
if (!check(a, c1, d1, d2)) {
a0 = c1;
} else {
a0 = c2;
}
if (!check(a, d1, c1, c2)) {
a1 = d1;
} else {
a1 = d2;
}
if (!check(b, c1, d1, d2)) {
b0 = c1;
} else {
b0 = c2;
}
if (!check(b, d1, c1, c2)) {
b1 = d1;
} else {
b1 = d2;
}
if(compare(a,b,a0,b1)||compare(a,b,a1,b0))puts("1");
else puts("2");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
input:
3 0 0 1 1 2 2 3 3 4 4 5 5 0 0 1 1 2 2 3 3 2 2 3 3 0 0 10 10 10 0 0 10 1 1 2 2
output:
0 0 1
result:
ok 3 number(s): "0 0 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 -999999999 999999998 999999999 999999998 -1000000000 -1000000000 1000000000 1000000000 1000000000 -1000000000 -1000000000 1000000000 -999999999 999999998 999999999 999999998 -999999998 -999999998 1000000000 1000000000 999999998 -999999998 -1000000000 1000000000
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
1 0 0 1 1 2 2 3 3 4 4 5 5
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 76ms
memory: 3876kb
input:
100000 -851839419 34688642 -667081997 395784949 -624068418 -155389155 119194510 -758711821 -992436155 -812775173 851861070 -592596572 974613003 -179673992 -485749861 520596304 -115838823 -265233646 -573799007 -222234500 608830643 -887109945 483106217 -906910755 -597593284 384264657 940783 476657007 ...
output:
0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 728910594 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 ...
result:
wrong answer 16th numbers differ - expected: '1', found: '728910594'