国产探花免费观看_亚洲丰满少妇自慰呻吟_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ā)表
主站蜘蛛池模板: 平凉市| 兰坪| 炉霍县| 呼伦贝尔市| 巧家县| 朔州市| 阿合奇县| 京山县| 马鞍山市| 清涧县| 保定市| 华安县| 海门市| 镶黄旗| 杨浦区| 东辽县| 高雄市| 墨江| 邓州市| 广丰县| 慈溪市| 寻甸| 登封市| 河北区| 阳泉市| 南溪县| 根河市| 定南县| 六盘水市| 垣曲县| 德安县| 江源县| 仲巴县| 盐津县| 吴川市| 龙川县| 苗栗县| 武威市| 鄂托克旗| 炎陵县| 巩留县|