CF350D.Looking for Owls

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Emperor Palpatine loves owls very much. The emperor has some blueprints with the new Death Star, the blueprints contain nn distinct segments and mm distinct circles. We will consider the segments indexed from 11 to nn in some way and the circles — indexed from 11 to mm in some way.

Palpatine defines an owl as a set of a pair of distinct circles (i,j)(i,j) ( i<j ) and one segment kk , such that:

  1. circles ii and jj are symmetrical relatively to the straight line containing segment kk ;
  2. circles ii and jj don't have any common points;
  3. circles ii and jj have the same radius;
  4. segment kk intersects the segment that connects the centers of circles ii and jj .

Help Palpatine, count the number of distinct owls on the picture.

输入格式

The first line contains two integers — nn and mm ( 1<=n<=31051<=n<=3·10^{5} , 2<=m<=15002<=m<=1500 ).

The next nn lines contain four integers each, x1x_{1} , y1y_{1} , x2x_{2} , y2y_{2} — the coordinates of the two endpoints of the segment. It's guaranteed that each segment has positive length.

The next mm lines contain three integers each, xix_{i} , yiy_{i} , rir_{i} — the coordinates of the center and the radius of the ii -th circle. All coordinates are integers of at most 10410^{4} in their absolute value. The radius is a positive integer of at most 10410^{4} .

It is guaranteed that all segments and all circles are dictinct.

输出格式

Print a single number — the answer to the problem.

Please, do not use the %lld specifier to output 64-bit integers is С++. It is preferred to use the cout stream or the %I64d specifier.

输入输出样例

  • 输入#1

    1 2
    3 2 3 -2
    0 0 2
    6 0 2
    

    输出#1

    1
    
  • 输入#2

    3 2
    0 0 0 1
    0 -1 0 1
    0 -1 0 0
    2 0 1
    -2 0 1
    

    输出#2

    3
    
  • 输入#3

    1 2
    -1 0 1 0
    -100 0 1
    100 0 1
    

    输出#3

    0
    

说明/提示

Here's an owl from the first sample. The owl is sitting and waiting for you to count it.

首页