QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669255#7065. Trianglesw7777TL 0ms3912kbC++203.0kb2024-10-23 17:53:082024-10-23 17:53:09

Judging History

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

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

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
double eps = 1e-9;
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();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -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:


result: