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

首頁 > 學院 > 開發設計 > 正文

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

2019-11-14 10:11:03
字體:
來源:轉載
供稿:網友

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個目標,給出N個目標點的坐標,并且給出機槍的目標。

這個機槍非常牛X,其開一槍,前后的人都會死。

問最少開多少槍,能夠將所有目標都打到。

思路:

問題尋找共性。

對于一條路徑上的所有目標都有一個唯一的共性,那就是斜率。

那么我們對問題的斜率進行處理即可。任務目標就是統計斜率的個數。

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

注意這個K需要用double類型。

過程用map維護一下第一次出現即可。

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);    }}


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 连南| 余姚市| 英吉沙县| 化德县| 靖宇县| 临汾市| 米林县| 宣武区| 开封市| 淳化县| 桐梓县| 东丰县| 永定县| 包头市| 娄底市| 土默特左旗| 荔浦县| 辽宁省| 西充县| 淅川县| 新龙县| 吴旗县| 濮阳市| 九龙县| 长治市| 镇江市| 夏津县| 剑河县| 株洲县| 宜兰县| 宁河县| 保康县| 比如县| 蓬溪县| 三门峡市| 南宁市| 甘德县| 昌乐县| 庆阳市| 丽水市| 龙江县|