链接：https://ac.nowcoder.com/acm/contest/338/D
来源：牛客网
题目描述
As everyone knows, there are now n people participating in the competition. It was finally lunch time after 3 hours of the competition. Everyone brought a triangular bread. When they were going to eat bread, some people found that they solved more problems than others, but their bread was smaller than others. They thought it was very unfair. In this case, they will forcibly exchange bread with the other party (may be exchanged many times, someone can still exchange with others after being exchanged if the above conditions are satisfied, the other party can not refuse).
The description of the bread is given by the coordinates of the three vertices of the triangle. The size of the bread is twice the size of the triangle area, ensuring that there are no two breads of the same size, and the number of problems each person makes is different.
Dandan is also one of the contestants. Now he knows the number of problems solved by each person and the description of the bread they bring. Now he wants to know that after all the exchanges are over (That is, there can be no more exchanges between any two people), The size of the bread he can get.
输入描述:
The first line gives an integer n, which indicates the number of people who participated in the competition.
Lines 2~n+1, each line gives 7 integers separated by spaces such as:
num x1 y1 x2 y2 x3 y3
num represents the number of the ith personal problem solving. (x1, y1) (x2, y2) (x3, y3) represents the coordinates of the three points of the bread of the triangle with the i-th person. ensure that three points are not in the same line.
Notice that the second line (the first person) represents Dandan's information.
Data guarantee: 0<n<=1e5，0<=num<1e9, -1e8<x1, x2, x3, y1, y2, y3<1e8.
输出描述:
Outputs an integer representing the size of the bread that DanDan eventually gets.
示例2
备注:
1e5=100000
1e8=100000000
1e9=1000000000
优化一下
显然，最终的局面为：解题数目排行第i的人会获得第i大的面包（解题数目最多的人一定可以 获得最大的面包，第二可以获得第二大的面包，依次类推…）。 故只需知道到Dandan的解题数目在所有人中的排名rk，然后输出第rk大的面包大小即可。 (Ⅰ)获取排名--排序：sort()。 (Ⅱ)已知三点坐标计算三角形的面积？ ①底×高/2--可能会有精度误差(?) ②向量叉乘： 如图三角形的面积为1 2 a × b ，故三角形的面积的两倍为 a × b 。
#include<stdio.h> #include<algorithm> using namespace std; int main() { int t; long long x; scanf("%d",&t); long long sum[100000+10]; long long n[100000+10]; long long a,b,c,d,e,f; for(int i = 0; i<t; i++) { scanf("%lld %lld %lld %lld %lld %lld %lld",&n[i],&a,&b,&c,&d,&e,&f); sum[i] = (a*d+c*f+e*b-a*f-c*b-e*d); if(sum[i]<0) sum[i] = -sum[i]; x = n[0]; } sort(n,n+t); sort(sum,sum+t); for(int i = 0; i < t; i++) { if(x==n[i]) { printf("%lld ",sum[i]); } } }
显然，最终的局面为：解题数目排行第i的人会获得第i大的面包（解题数目最多的人一定可以获得最大的面包，第二可以获得第二大的面包，依次类推…）。故只需知道到Dandan的解题数目在所有人中的排名rk，然后输出第rk大的面包大小即可。(Ⅰ)获取排名--排序：sort()。(Ⅱ)已知三点坐标计算三角形的面积？①底×高/2--可能会有精度误差(?)②向量叉乘：如图三角形的面积为12a × b ，故三角形的面积的两倍为 a × b 。