题目描述给定一组线段代表倾斜的平面从某一源点垂直下落的水滴在碰到某条线段后会沿该线段滑落至其较低端点然后继续垂直下落如此反复直至落到地面假设地面为y0y 0y0。给定若干源点需要计算每个源点的水滴最终落到地面时的xxx坐标。线段不水平、不相交且所有点的xxx坐标互不相同包括端点与源点。输入格式第一行为测试用例个数随后有一个空行。每个测试用例第一行为整数NPNPNP表示线段数量。接下来NPNPNP行每行四个整数x1,y1,x2,y2x_1, y_1, x_2, y_2x1,y1,x2,y2表示一条线段的两端点坐标。下一行为整数NSNSNS表示源点数量。接下来NSNSNS行每行两个整数x,yx, yx,y表示源点坐标。各测试用例之间有一个空行。输出格式对于每个测试用例输出NSNSNS行每行一个整数为对应源点的最终落地点xxx坐标顺序与输入一致。不同测试用例输出之间用一个空行分隔。样例输入1 4 14 7 3 4 11 13 16 11 1 10 6 7 2 1 4 3 3 10 4 14 14 2 13样例输出10 16 2题目分析水滴的运动可分解为垂直下落和沿斜面滑落两个阶段。由于线段非水平且不相交每个源点最终会沿一条唯一的线段序列滑落直到无法再碰到任何线段此时水滴垂直落到地面。因为所有点xxx坐标互不相同线段端点也不会在垂直投影上重合故判定某点是否在线段上可通过叉积精确判断。每条线段在一次下落过程中最多被经过一次水不会重复滑过同一斜面因此可用标记避免循环。解题思路对于每个源点重复以下过程步骤1\texttt{1}1. 从当前点PPP开始遍历所有线段检查PPP是否在该线段上包括端点。步骤2\texttt{2}2. 若PPP在某线段上则将PPP更新为该线段的较低端点即yyy坐标较小的端点并标记该线段已被当前源点使用然后重复步骤1\texttt{1}1。步骤3\texttt{3}3. 若PPP不在任何线段上则停止循环输出PPP的xxx坐标。由于每条线段只能被同一源点使用一次标记保证不会无限循环。线段按较高端点的高度降序排列可优化查找但NPNPNP较小未说明但通常较小直接遍历即可。点在线段上的判定利用叉积cp(a,b,c)(bx−ax)(cy−ay)−(by−ay)(cx−ax)cp(a,b,c) (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)cp(a,b,c)(bx−ax)(cy−ay)−(by−ay)(cx−ax)若cp0cp 0cp0且ppp的xxx坐标在端点xxx范围内则ppp在线段上。代码实现// Water Falls// UVa ID: 833// Verdict: Accepted// Submission Date: 2016-12-09// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpoint{intx,y;};structsegment{point left,right,lower;intflag;booloperator(constsegments)const{returnmax(left.y,right.y)max(s.left.y,s.right.y);}};// 叉积判断点abc组成的两条线段的转折方向。当叉积大于0则形成一个右拐// 否则共线cp 0或左拐cp 0。intcp(constpointa,constpointb,constpointc){return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}// 从点a向点b望去点c位于线段ab的左侧或在线段上返回true。boolccw(constpointa,constpointb,constpointc){returncp(a,b,c)0;}boolpointOnSegment(constpointp,constsegments){returnp.xs.left.xp.xs.right.xccw(s.left,s.right,p);}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;cincases;point point1,point2,lower,point3;for(intc1;ccases;c){if(c1)cout\n;intNP;cinNP;vectorsegmentsegments;for(inti1;iNP;i){cinpoint1.xpoint1.ypoint2.xpoint2.y;if(point1.xpoint2.x)swap(point1,point2);if(point1.ypoint2.y)lowerpoint1;elselowerpoint2;segments.push_back((segment){point1,point2,lower,0});}sort(segments.begin(),segments.end());intNS;cinNS;for(inti1;iNS;i){cinpoint3.xpoint3.y;while(true){boolupdatedfalse;for(intj0;jsegments.size();j)if(segments[j].flagipointOnSegment(point3,segments[j])){point3segments[j].lower;segments[j].flagi;updatedtrue;break;}if(!updated)break;}coutpoint3.x\n;}}return0;}总结本题通过模拟水滴的垂直下落与斜面滑落过程利用线段上的点判定和标记避免循环求出最终落地点。关键在于正确判断点是否在线段上以及每次滑落后更新当前点为低端点。由于线段互不相交且xxx坐标无重合判定简单可靠。算法时间复杂度为O(NS×NP×滑落次数)O(NS \times NP \times \text{滑落次数})O(NS×NP×滑落次数)但滑落次数受线段数量限制且NPNPNP通常较小足够高效。该解法体现了几何模拟与标记技巧的结合。 UVa 833 Water Falls
题目描述给定一组线段代表倾斜的平面从某一源点垂直下落的水滴在碰到某条线段后会沿该线段滑落至其较低端点然后继续垂直下落如此反复直至落到地面假设地面为y0y 0y0。给定若干源点需要计算每个源点的水滴最终落到地面时的xxx坐标。线段不水平、不相交且所有点的xxx坐标互不相同包括端点与源点。输入格式第一行为测试用例个数随后有一个空行。每个测试用例第一行为整数NPNPNP表示线段数量。接下来NPNPNP行每行四个整数x1,y1,x2,y2x_1, y_1, x_2, y_2x1,y1,x2,y2表示一条线段的两端点坐标。下一行为整数NSNSNS表示源点数量。接下来NSNSNS行每行两个整数x,yx, yx,y表示源点坐标。各测试用例之间有一个空行。输出格式对于每个测试用例输出NSNSNS行每行一个整数为对应源点的最终落地点xxx坐标顺序与输入一致。不同测试用例输出之间用一个空行分隔。样例输入1 4 14 7 3 4 11 13 16 11 1 10 6 7 2 1 4 3 3 10 4 14 14 2 13样例输出10 16 2题目分析水滴的运动可分解为垂直下落和沿斜面滑落两个阶段。由于线段非水平且不相交每个源点最终会沿一条唯一的线段序列滑落直到无法再碰到任何线段此时水滴垂直落到地面。因为所有点xxx坐标互不相同线段端点也不会在垂直投影上重合故判定某点是否在线段上可通过叉积精确判断。每条线段在一次下落过程中最多被经过一次水不会重复滑过同一斜面因此可用标记避免循环。解题思路对于每个源点重复以下过程步骤1\texttt{1}1. 从当前点PPP开始遍历所有线段检查PPP是否在该线段上包括端点。步骤2\texttt{2}2. 若PPP在某线段上则将PPP更新为该线段的较低端点即yyy坐标较小的端点并标记该线段已被当前源点使用然后重复步骤1\texttt{1}1。步骤3\texttt{3}3. 若PPP不在任何线段上则停止循环输出PPP的xxx坐标。由于每条线段只能被同一源点使用一次标记保证不会无限循环。线段按较高端点的高度降序排列可优化查找但NPNPNP较小未说明但通常较小直接遍历即可。点在线段上的判定利用叉积cp(a,b,c)(bx−ax)(cy−ay)−(by−ay)(cx−ax)cp(a,b,c) (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)cp(a,b,c)(bx−ax)(cy−ay)−(by−ay)(cx−ax)若cp0cp 0cp0且ppp的xxx坐标在端点xxx范围内则ppp在线段上。代码实现// Water Falls// UVa ID: 833// Verdict: Accepted// Submission Date: 2016-12-09// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpoint{intx,y;};structsegment{point left,right,lower;intflag;booloperator(constsegments)const{returnmax(left.y,right.y)max(s.left.y,s.right.y);}};// 叉积判断点abc组成的两条线段的转折方向。当叉积大于0则形成一个右拐// 否则共线cp 0或左拐cp 0。intcp(constpointa,constpointb,constpointc){return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}// 从点a向点b望去点c位于线段ab的左侧或在线段上返回true。boolccw(constpointa,constpointb,constpointc){returncp(a,b,c)0;}boolpointOnSegment(constpointp,constsegments){returnp.xs.left.xp.xs.right.xccw(s.left,s.right,p);}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;cincases;point point1,point2,lower,point3;for(intc1;ccases;c){if(c1)cout\n;intNP;cinNP;vectorsegmentsegments;for(inti1;iNP;i){cinpoint1.xpoint1.ypoint2.xpoint2.y;if(point1.xpoint2.x)swap(point1,point2);if(point1.ypoint2.y)lowerpoint1;elselowerpoint2;segments.push_back((segment){point1,point2,lower,0});}sort(segments.begin(),segments.end());intNS;cinNS;for(inti1;iNS;i){cinpoint3.xpoint3.y;while(true){boolupdatedfalse;for(intj0;jsegments.size();j)if(segments[j].flagipointOnSegment(point3,segments[j])){point3segments[j].lower;segments[j].flagi;updatedtrue;break;}if(!updated)break;}coutpoint3.x\n;}}return0;}总结本题通过模拟水滴的垂直下落与斜面滑落过程利用线段上的点判定和标记避免循环求出最终落地点。关键在于正确判断点是否在线段上以及每次滑落后更新当前点为低端点。由于线段互不相交且xxx坐标无重合判定简单可靠。算法时间复杂度为O(NS×NP×滑落次数)O(NS \times NP \times \text{滑落次数})O(NS×NP×滑落次数)但滑落次数受线段数量限制且NPNPNP通常较小足够高效。该解法体现了几何模拟与标记技巧的结合。