当前位置:编程学习 > C/C++ >>

POJ 1408 Fishnet 两线段交点坐标

设线段v1v2,u1u2。
 
t = (v2-v1)*(u1-v1)/(v2-v1)*(u2-u1);  即两个平行四边形的面积之比。
 
交点坐标为p = {u1.x + (u2.x-u1.x)*t , u1.y + (u2.y-u.y)*t};
 
前提是两线段相交。
 
 
 
#include <cstdio>  
#include <cmath>  
#include <algorithm>  
  
using namespace std;  
  
struct P  
{  
    double x,y;  
}t[35],b[35],l[35],r[35],fishnet[35][35];  
  
double CrossProduct(P a1,P a2,P b1,P b2)  
{  
    P v1 = {a1.x - a2.x,a1.y - a2.y};  
    P v2 = {b1.x - b2.x,b1.y - b2.y};  
    return (v1.x*v2.y - v1.y*v2.x);  
}  
  
  
P CalLineCrossPosition(P a1,P a2,P b1,P b2)  
{  
      
    double t;  
    t = fabs(CrossProduct(a1,b1,a1,a2))/fabs(CrossProduct(a1,a2,b1,b2));  
    P p = {b1.x + (b2.x-b1.x)*t,b1.y + (b2.y-b1.y)*t};  
    return p;  
}  
  
int main()  
{  
    int n,i,j;  
    double MaxArea,TempArea;  
    while(scanf("%d",&n) && n)  
    {  
        for(i = 1;i <= n ; ++i)  
        {     
            b[i].y = 0;  
            scanf("%lf",&b[i].x);  
        }  
        for(i = 1;i <= n ; ++i)  
        {  
            t[i].y = 1;  
            scanf("%lf",&t[i].x);  
        }  
        for(i = 1;i <= n ; ++i)  
        {  
            l[i].x = 0;  
            scanf("%lf",&l[i].y);  
        }  
        for(i = 1;i <= n ; ++i)  
        {     
            r[i].x = 1;  
            scanf("%lf",&r[i].y);  
        }  
  
        ++n;  
  
        for(i = 1;i < n; ++i)  
        {  
            for(j = 1;j < n; ++j)  
            {  
                fishnet[i][j] = CalLineCrossPosition(l[i],r[i],t[j],b[j]);  
            }  
        }  
  
        for(i = 1;i < n; ++i)  
        {  
            fishnet[i][n] = r[i];  
            fishnet[i][0] = l[i];  
            fishnet[0][i] = b[i];  
            fishnet[n][i] = t[i];  
        }  
  
        MaxArea = -199;  
          
          
        fishnet[0][0].x = 0;  
        fishnet[0][0].y = 0;  
        fishnet[0][n].x = 1;  
        fishnet[0][n].y = 0;  
        fishnet[n][0].x = 0;  
        fishnet[n][0].y = 1;  
        fishnet[n][n].x = 1;  
        fishnet[n][n].y = 1;  
  
        for(i = 0;i < n; ++i)  
        {  
            for(j = 0;j < n; ++j)  
            {  
                TempArea = (fabs(CrossProduct(fishnet[i][j],fishnet[i+1][j],fishnet[i][j],fishnet[i][j+1]))+fabs(CrossProduct(fishnet[i+1][j+1],fishnet[i+1][j],fishnet[i+1][j+1],fishnet[i][j+1])))/2;  
                if(MaxArea < TempArea)  
                    MaxArea = TempArea;  
            }  
        }  
        printf("%.6f\n",MaxArea);  
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,