7-15 水果忍者 (计算几何+思维)

    科技2025-11-03  9

    #include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; const int N=1e4+100; struct P{ double x,y1,y2; }a[N]; int main(){ int n;scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf%lf%lf",&a[i].x,&a[i].y1,&a[i].y2); } double ans1,ans2; for(int i=0;i<n;i++){ double upmn=INF,domx=-INF; int j; for(j=0;j<n;j++){ if(i==j) continue; bool f=false; double up=(a[j].y1-a[i].y2)/(a[j].x-a[i].x); double down=(a[j].y2-a[i].y2)/(a[j].x-a[i].x); if(up<down){ swap(up,down); f=true; } if(down>upmn||up<domx) break; domx=max(down,domx); if(up<upmn){ upmn=up; ans1=a[j].x; ans2=a[j].y1; if(f) ans2=a[j].y2; } } if(j==n){ printf("%.0lf %.0lf %.0lf %.0lf\n",a[i].x,a[i].y2,ans1,ans2); break; } } return 0; }

     

    Processed: 0.010, SQL: 8