P3476 [POI2008]TRO-Triangles

    • 10通过
    • 83提交
  • 题目提供者洛谷OnlineJudge
  • 标签 叉积 深度优先搜索,DFS 计算几何 POI 2008 高性能
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    pairwise disjoint points in the plane are given ().

    There are triangles whose vertices are some pairwise different points among them (including degenerate triangles, i.e. ones whose vertices are collinear).

    We want to calculate the sum of areas of all the triangles with vertices in the given points.

    Those parts of the plane that belong to many triangles are to be calculated multiple times. We assume that the area of degenerate triangles (i.e. those with collinear vertices) is zero.

    Task Write a programme that:

    reads from the standard input the coordinates of the points in the plane, determines the sum of the areas of all the triangles with vertices in the given points, prints out the result to the standard output.

    给定平面上的一些点,求这些点能组成的所有三角形的面积之和

    输入输出格式

    输入格式:

    In the first line of the standard input there is one integer () denoting the number of selected points.

    Each of the following lines contains two integers and () separated by a single space and denoting the coordinates of the point (for ).

    No pair (ordered) of coordinates appears more than once.

    输出格式:

    In the first and only line of the standard output there should be one real number equal to the sum of the areas of all the triangles with vertices in the given points. The outcome should be printed out with exactly one digit after dot and should not differ from the correct value by more than .

    输入输出样例

    输入样例#1: 复制
    5
    0 0
    1 2
    0 2
    1 0
    1 1
    
    输出样例#1: 复制
    7.0
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。