QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#669259#7065. Trianglesw7777TL 996ms3912kbC++203.0kb2024-10-23 17:53:552024-10-23 17:53:57

Judging History

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

  • [2024-10-23 17:53:57]
  • 评测
  • 测评结果:TL
  • 用时:996ms
  • 内存:3912kb
  • [2024-10-23 17:53:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
double eps = 1e-7;
class Point
{

public:
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}

    double operator ^(const Point &b)const{
        return x*b.y - b.x*y;
    }
    double operator *(const Point &b)const{
        return x*b.x+y*b.y;
    }
    Point operator - (Point p){
        return Point(x - p.x , y - p.y);
    }
    bool operator == (const Point &p) const{
        return fabs(x - p.x)<1e-10&&fabs(y-p.y)<1e-10;
    }
    
}p[3];
typedef Point Vector;
double cross(Vector a,Vector b){
    return fabs(a.x*b.y - a.y*b.x);
}

int dcmp(double x){
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}
bool onseg(Point p1,Point p2,Point q){
    return dcmp((p1 - q) ^ (p2 - q)) == 0&&dcmp((p1 - q)*(p2 - q)) <= 0;
}
double area(Point p0,Point p1,Point p2){
    double k = p0.x*p1.y + p1.x*p2.y + p2.x*p0.y - p1.x*p0.y - p2.x*p1.y - p0.x*p2.y;
    return fabs(k/2);
}
void solve(){
    for(int i = 0;i<3;i++){
            cin>>p[i].x>>p[i].y;
        }
        int x,y;
        cin>>x>>y;
        Point Q(x,y);
        for(int i = 0;i<3;i++){
            if(Q == p[i]){
                cout<<fixed<<setprecision(10)<<(p[(i+1)%3].x+p[((i+2)%3)].x)/2<<" "<<
                (p[(i+1)%3].y+p[((i+2)%3)].y)/2<<endl;
                return;
            }
        }
        double ans = area(p[0],p[1],p[2])/2;
        for(int i = 0;i<3;i++){
            if(onseg(p[(i+1)%3],p[(i+2)%3],Q)){
                Point ll = p[(i+1)%3] ,rr = p[(i+2)%3];
                if(area(ll,p[i],Q) < area(rr,p[i],Q)){
                    //rbian
                    Point l = p[i],r = rr;
                    while(1){
                        Point mid((l.x+r.x)/2,(l.y+r.y)/2);
                        if(fabs(area(Q,mid,rr) - ans)<eps){
                            
                            cout<<fixed<<setprecision(10)<<mid.x<<" "<<mid.y<<endl;
                            return;
                        }
                        //cout<<area(Q,mid,rr)<<endl;
                        if(area(Q,mid,rr) > ans) l = mid;
                        else r = mid;
                        
                    }
                }
                else{
                    Point l = p[i],r = ll;
                    while(1){
                        Point mid((l.x+r.x)/2,(l.y+r.y)/2);
                        if(fabs(area(Q,mid,ll) - ans)<eps){
                            cout<<fixed<<setprecision(10)<<mid.x<<" "<<mid.y<<endl;
                            return;
                        }
                        if(area(Q,mid,ll) > ans) l = mid;
                        else r = mid;
                    }
                }
            }
            else continue;
        }
        cout<<-1<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t -- ){
        solve();
    }
}

詳細信息

Test #1:

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

input:

2
0 0 1 1 1 0 1 0
0 0 1 1 1 0 2 0

output:

0.5000000000 0.5000000000
-1

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 993ms
memory: 3912kb

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
21424.6814794177 13086.0539109842
-1
-1
18711.2379903041 10162.3763772587
-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
28212.9521348926 245.8177862388
-1
-1
-1
-1
-1
-1
-1
-1
22604.5753021888 14546.1287161058
-1
-1
11557.3465218991 46...

result:

ok 1111378 numbers

Test #3:

score: 0
Accepted
time: 996ms
memory: 3720kb

input:

999974
9228 16833 13143 23461 5117 7645 21359 13652
21313 3160 20333 1620 16288 7781 13315 10132
4372 0 27536 0 3207 8695 9983 0
21469 29998 19948 29904 30517 11141 14857 12881
11116 29172 16833 32095 18915 9448 22043 12275
32131 0 14304 0 16638 29018 2048 0
4695 4823 14130 2496 32676 4092 6363 2476...

output:

-1
-1
11482.9903720162 5737.2238363812
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
15409.8418549346 12451.4278636544
-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
10828.9713857796 25347.3348573230
-1
-1
-1
-1
-1
18768.6726994647 12151.3671509899
-1
-1
-1
-1
-1
10801.120...

result:

ok 1110866 numbers

Test #4:

score: -100
Time Limit Exceeded

input:

1000000
54242 34392 23333 92971 5711 47765 54242 34392
24492 41078 36756 68794 2060 62118 14678 50283
12685 18891 59613 23256 26016 46755 59613 23256
85238 49611 95092 85360 45143 87657 95092 85360
72852 37174 39825 60628 32289 18423 72852 37174
95309 61613 1645 45877 78395 38196 95309 61613
92215 7...

output:


result: