关于种地的忧伤故事
Problem:A
Time Limit:1000ms
Memory Limit:65536K
Description
“ 改革春风吹满地,
不会AC没关系;
实在不行回老家，
还有一亩三分地。
谢谢!（乐队奏乐）”
话说部分学生心态极好，每天就知道游戏，寒假集训如此简单的题目，也是云里雾里，而且，还竟然来这么几句打油诗。
好呀，学长的责任就是帮你解决问题，既然想种田，那就分你一块。
这块田位于黑龙江省NEFU大学皇家帽儿山林场，多边形形状的一块地，原本是荣大小姐的，现在就准备送给你了。
不过，任何事情都没有那么简单，你必须首先告诉我这块地到底有多少面积，如果回答正确才能真正得到这块地。
发愁了吧？就是要让你知道，种地也是需要AC知识的！以后还是好好练吧...
Input
输入数据包含多个测试实例，每个测试实例占一行，每行的开始是一个整数n(3<=n<=100)，它表示多边形的边数（当然也是顶点数），
然后是按照逆时针顺序给出的n个顶点的坐标（x1, y1, x2, y2... xn, yn）,为了简化问题，这里的所有坐标都用整数表示。
输入数据中所有的整数都在32位整数范围内，n=0表示数据的结束，不做处理。
Output
对于每个测试实例，请输出对应的多边形面积，结果精确到小数点后一位小数。
每个实例的输出占一行。
Sample Input
3 0 0 1 0 0 1
4 1 0 0 1 -1 0 0 -1
0
#include <cstdio>
#include <cmath>
#define MAX 1000
using namespace std;
typedef struct A
{
double x,y;
}POINT;
POINT p[MAX];
double mul_cross(POINT a,POINT b)
{
return ((a.x-p[0].x)*(b.y-p[0].y)-(a.y-p[0].y)*(b.x-p[0].x));
}
int main()
{
int n;
double sum;
while(scanf("%d",&n)&&n)
{
sum=0.0;
for(int i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=1;i<n-1;i++)
sum+=mul_cross(p[i],p[i+1]);
printf("%.1f\n",fabs(sum)/2);
}
return 0;
}
叉积求距离
Problem:B
Time Limit:1000ms
Memory Limit:65536K
Description
实验室胡某是LOL一区最强王者，其上分神器就是ADCarry中的皮城女警。话说这女警不但长的好看，手还是全联盟最长的。
女警的R技能完美一击呢，其实就是点爆对方的头，简称爆头。所谓爆头，就是子弹直接命中对方的头部，以秒杀敌人。
现在用一个三维的直角坐标系来描述游戏中的三维空间（水平面为xoy平面，z轴正方向是上方）。
假设游戏中角色的头是一个标准的球。告诉你对面暴走金克斯的身高，头部半径，所站位置的坐标；
胡某所控女警的身高，头部半径，所站位置的坐标，以及枪头所指方向的单位向量。
女警的枪瞄准时枪膛中的子弹跟视线基本同线，我们忽略它们的距离，就当成同线。
金克斯呢，很是嚣张地正立着。现在女警正在瞄准，由于瞄准时身体微弯，视线从头心出发，他头部的实际高度比正立时低10%。
你的任务就是，计算女警在这一刻扣下扳机，能否爆金克斯的头。
注意：这里忽略子弹的直径和重力作用，也就是说子弹是无限小的，弹道是一条笔直的射线，两人之间没有障碍物。
并且只要子弹擦到头部，哪怕是边缘，也算爆头。
Input
测试数据的第一行有一个正整数T，表示有T组测试数据。
每组数据的第一行有五个实数，h1,r1,x1,y1,z1，分别表示金克斯的身高，头部半径以及所站的位置。
第二行有八个实数，h2,r2,x2,y2,z2,x3,y3,z3，分别表示女警的身高，头部半径，所站位置，以及枪头所指方向的方向向量。
Output
每一组输入数据对应一行输出。如果能爆金克斯的头，输出"Boom",否则输出"Pity"。
Sample Input
2
1.62 0.1 10.0 10.0 10.0
1.80 0.09 0.0 0.0 0.0 1.0 1.0 1.0
1.62 0.1 0.0 0.0 0.0
1.80 0.09 10.0 10.0 10.0 -1.0 -1.0 -1.0
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
double h1,r1,x1,y1,z1;
double h2,r2,x2,y2,z2,x3,y3,z3;
scanf("%lf%lf%lf%lf%lf",&h1,&r1,&x1,&y1,&z1);
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&h2,&r2,&x2,&y2,&z2,&x3,&y3,&z3);
double k1=z1+h1-r1;
double k2=z2+0.9*h2-r2;
double a=x1-x2,b=y1-y2,c=k1-k2;
double a1=b*z3-y3*c,b1=a*z3-x3*c,c1=a*y3-b*x3;
double dis=(a1*a1+b1*b1+c1*c1)/(x3*x3+y3*y3+z3*z3);
if(dis<=r1*r1&&(a*x3+b*y3+c*z3>0))
printf("Boom\n");
else
printf("Pity\n");
}
return 0;
}
3.4这两个题你们看群里有当时的题解定义结构体用了vector，这个是关键字，自己定义变量不能用！
线段相交
Problem:C
Time Limit:1000ms
Memory Limit:65536K
Description
课件中***丝学长关于线段相交可是讲的很清楚很彻底了，这道线段相交的水题就当做是下道题的铺垫吧。
Input
输入数据有多组，每组第一行有一个整数n，表示测试实例的数目，接下来有n行，每行8个数，分别表示2条线段的起点和终点：
线段1：（x1,y1）(x2,y2)
线段2： (x3,y3) (x4,y4)
n=0表示输入结束，该组不做任何处理。
Output
你的任务就是，对于每组输入，判断他们是否相交。相交输出“YES”，否则输出“no”；
Sample Input
2
0 0 0 1 1 0 1 1
0 0 0 1 0 0 0 1
0
#include <stdio.h>
struct Point{
double x,y;
};
int cross(struct Point a,struct Point b,struct Point c){
double x1 = b.x-a.x;
double y1 = b.y-a.y;
double x2 = c.x-a.x;
double y2 = c.y-a.y;
return x1*y2-x2*y1;
}
double min(double a,double b){
if(a < b)return a;
else return b;
}
double max(double a,double b){
if(a > b)return a;
else return b;
}
int check(struct Point a,struct Point b,struct Point c,struct Point d){
if(max(a.x,b.x) < min(c.x,d.x))return 0;
if(max(a.y,b.y) < min(c.y,d.y))return 0;
if(max(c.x,d.x) < min(a.x,b.x))return 0;
if(max(c.y,d.y) < min(a.y,b.y))return 0;
if(cross(a,c,d)*cross(b,c,d) <= 0 && cross(c,a,b)*cross(d,a,b) <= 0)
return 1;
else return 0;
}
int main()
{
struct Point a,b,c,d;
int n;
while(scanf("%d",&n) ==1 && n){
while(n--){
scanf("%lf%lf",&a.x,&a.y);
scanf("%lf%lf",&b.x,&b.y);
scanf("%lf%lf",&c.x,&c.y);
scanf("%lf%lf",&d.x,&d.y);
if(check(a,b,c,d))printf("YES\n");
else printf("no\n");
}
}
return 0;
}
线段相交进化版
Problem:D
Time Limit:1000ms
Memory Limit:65536K
Description
欧巴马有n根长度不同的木棒，他喜欢把这些木棒任意的丢在地板上来玩耍。因为木棒都是随意丢在地板上的，难免会些木棒相交，
对于那些相交的木棒，他们就有了上下之分，后来丢出的木棒当然在之前丢出木棒的上方，你的任务就是，找出这些位于最上方的木棒，
所谓在最上方，就是某跟木棒上方没有其他的木棒，当然，一根单独的木棒是符合“最上方”的标准的，因为它上方确实没有其他的木棒。
Input
输入数据有多组，每组以一个整数n开始，表示有n跟木棒，木棒的标号为1,2,3...n。
接下来有n行，每行4个数，表示每根木棒在平面直角坐标系中的起点和终点的坐标（x1,y1）(x2,y2);
n=0表示输入结束，该组不做任何处理。
Output
对于每组输入，输出位于最上方的木棒的标号，每组输出占一行。
Sample Input
5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0
Sample Output
Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.
#include <iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef struct Node
{
double x,y;
}Point;
typedef struct line
{
Point start,end;
}vector;
double multi(Point p1,Point p2,Point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int cross(vector v1,vector v2)
{
if(max(v1.start.x,v1.end.x)>=min(v2.start.x,v2.end.x)&&
max(v2.start.x,v2.end.x)>=min(v1.start.x,v1.end.x)&&
max(v1.start.y,v1.end.y)>=min(v2.start.y,v2.end.y)&&
multi(v2.start,v1.end,v1.start)*multi(v1.end,v2.end,v1.start)>=0&&
multi(v1.start,v2.end,v2.start)*multi(v2.end,v1.end,v2.start)>=0)
return 1;
return 0;
}
int main()
{
// freopen("data.in.txt","r",stdin);
//freopen("data.out.txt","w",stdout);
int n;
vector p[1000];
int pl[1000];//是否有相交的
//int a[1000];//上面没有木棍的编号
//int k=0;
while(~scanf("%d",&n)&&n)
{
memset(pl,0,sizeof(pl));
//memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&p[i].start.x,&p[i].start.y,&p[i].end.x,&p[i].end.y);
}
for(int i=1;i<n;i++)//先扔的
{
for(int j=i+1;j<=n;j++)//后扔的
{
if(cross(p[i],p[j]))
{
pl[i]=1;
//printf("%d ",i);
}
}
//printf("\n");
}
printf("Top sticks:");
int m;
for(m=1;m<=n;m++)
{
if(!pl[m]) {printf("%d",m);m++;break;}
}
for(;m<=n;m++)
{
if(!pl[m]) printf(", %d",m);
}
printf(".\n");
}
return 0;
}
最最难的题
Problem:E
Time Limit:1000ms
Memory Limit:65536K
Description
什么是最最难的题呢，当然就是计算三角形的面积啦，像我们这样皇家林业大学的ACMer们，AC这样的问题简直ius浪费生命，
不过也没办法，上面有命令在先，出题一定要水，唉。你们就将就着做吧...
Input
输入数据第一行是一个整数n，表示有n组测试实例，接下来有n行，每行6个数，分别表示三角形三个顶点的坐标x1，y1，x2，y2，x3，y3；
（输入保证三个点不共线）
Output
对于每组坐标，输出由这三个顶点构成的三角形的面积，结果保留两位小数。每组输出占一行。
#include <cstdio>
#include <cmath>
#define MAX 1000
using namespace std;
typedef struct A
{
double x,y;
}POINT;
double mul_cross(POINT a,POINT b,POINT c)
{
return (a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y);
}
int main()
{
int n;
double sum;
POINT p[3];
scanf("%d",&n);
while(n--)
{
for(int i=0;i<3;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sum=mul_cross(p[0],p[1],p[2]);
printf("%.2f\n",fabs(sum)/2);
}
return 0;
}
京公网安备 11010502036488号