国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

Codeforces 514B Han Solo and Lazer Gun【思維】

2019-11-14 10:39:15
字體:
供稿:網(wǎng)友

B. Han Solo and Lazer Guntime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are n Imperial stormtroopers on the field. The battle field is a plane with Cartesian coordinate system. Each stormtrooper is associated with his coordinates(x,?y) on this plane.

Han Solo has the newest duplex lazer gun to fight these stormtroopers. It is situated at the point(x0,?y0). In one shot it can can destroy all the stormtroopers, situated on some line that crosses point(x0,?y0).

Your task is to determine what minimum number of shots Han Solo needs to defeat all the stormtroopers.

The gun is the newest invention, it shoots very quickly and even after a very large number of shots the stormtroopers don't have enough time to realize what's happening and change their location.

Input

The first line contains three integers n,x0 и y0 (1?≤?n?≤?1000,?-?104?≤?x0,?y0?≤?104) — the number of stormtroopers on the battle field and the coordinates of your gun.

Next n lines contain two integers each xi, yi (?-?104?≤?xi,?yi?≤?104) — the coordinates of the stormtroopers on the battlefield. It is guaranteed that no stormtrooper stands at the same point with the gun. Multiple stormtroopers can stand at the same point.

Output

PRint a single integer — the minimum number of shots Han Solo needs to destroy all the stormtroopers.

ExamplesInput
4 0 01 12 22 0-1 -1Output
2Input
2 1 21 11 0Output
1Note

Explanation to the first and second samples from the statement, respectively:

題目大意:

一共有N個(gè)目標(biāo),給出N個(gè)目標(biāo)點(diǎn)的坐標(biāo),并且給出機(jī)槍的目標(biāo)。

這個(gè)機(jī)槍非常牛X,其開一槍,前后的人都會(huì)死。

問最少開多少槍,能夠?qū)⑺心繕?biāo)都打到。

思路:

問題尋找共性。

對(duì)于一條路徑上的所有目標(biāo)都有一個(gè)唯一的共性,那就是斜率。

那么我們對(duì)問題的斜率進(jìn)行處理即可。任務(wù)目標(biāo)就是統(tǒng)計(jì)斜率的個(gè)數(shù)。

K=(y-y0)/(x-x0);

注意這個(gè)K需要用double類型。

過程用map維護(hù)一下第一次出現(xiàn)即可。

Ac代碼:

#include<stdio.h>#include<string.h>#include<map>using namespace std;int main(){    int n;    int x,y;    while(~scanf("%d%d%d",&n,&x,&y))    {        int flag1=0;        int flag2=0;        int output=0;        map<double ,int >s;        for(int i=0;i<n;i++)        {            int xx,yy;            scanf("%d%d",&xx,&yy);            if(xx==x)            {                flag1=1;                continue;            }            if(yy==y)            {                flag2=1;                continue;            }            double  k=(yy-y)*1.0/(xx-x)*1.0;            if(s[k]==0)            {                s[k]=1;                output++;            }        }        printf("%d/n",output+flag1+flag2);    }}


發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 满洲里市| 东安县| 富平县| 嘉鱼县| 泸州市| 安西县| 双牌县| 海门市| 滕州市| 诸暨市| 宜城市| 大悟县| 绍兴市| 三原县| 罗甸县| 新余市| 仁布县| 登封市| 巴彦县| 颍上县| 黄梅县| 桃园市| 柳河县| 常德市| 阿尔山市| 凌海市| 桓台县| 正蓝旗| 北川| 平邑县| 东明县| 车致| 罗江县| 阳春市| 从江县| 襄汾县| 本溪| 贵阳市| 南川市| 德钦县| 金门县|