[noip模拟题]合理种植
2024-10-19 04:24:27
【问题描述】
大COS在氯铯石料场干了半年,受尽了劳苦,终于决定辞职。他来到表弟小cos的寒树中学,找到方克顺校长,希望寻个活干。
于是他如愿以偿接到了一个任务……
美丽寒树中学种有许多寒树。方克顺希望校园无论从什么角度看都是满眼寒树,因此他不希望有三棵甚至更多寒树种在一条直线上。现在他把校园里n棵寒树的坐标都给了大COS,让他数出存在多少多树共线情况。(若一条直线上有三棵或以上的树,则算出现一个多树共线情况。)
【输入】
输入文件名为plant.in。
第1行一个正整数n,表示寒树棵数。
接下来n行,每行两个非负整数x、y,表示一颗寒树的坐标。没有两颗寒树在同一位置。
【输出】
输出文件名为plant.out。
输出一个整数,表示存在多少多树共线情况。
【输入输出样例】
plant.in |
plant.out |
6 0 0 1 1 2 2 3 3 0 1 1 0 |
1 |
【数据范围】
对于30%的数据,有n≤10;
对于50%的数据,有n≤100;
对于100%的数据,有n≤1,000,0≤x,y≤10,000。
这道题纯属数学题,先O(n2)跑一道,把任意两点之间的斜率求出来,再用O(n3)判断三条个点是否共线,至于判重嘛。。就自己想一下了
(论常数的重要性)
Code
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("plant.in");
ofstream fout("plant.out");
typedef bool boolean;
typedef class Point{
public:
int x;
int y;
}Point;
istream& operator >>(istream& in,Point& p){
in>>p.x>>p.y;
}
Point *ps;
int n;
int _x,_y;
long long ks[][];
boolean vis[][];
long long result = ;
int main(){
fin>>n;
memset(vis, false, sizeof(vis));
ps = new Point[(const int)(n + )];
for(int i = ;i <= n;i++)
fin>>ps[i];
for(int i = ;i <= n;i++){
for(int j = i + ;j <= n;j++){
_x = ps[j].x - ps[i].x;
_y = ps[j].y - ps[i].y;
if(_x == ) ks[i][j] = ;
else ks[i][j] = (_y * 100000000LL)/_x;
}
}
for(int i = ;i < n - ;i++){
for(int j = i + ; j < n;j++){
for(int k = j + ; k <= n;k++){
if(ks[i][j] == ks[j][k] && ks[i][j] == ks[i][k]){
if(vis[i][j]||vis[j][k]||vis[i][k]){
vis[i][j] = vis[j][k] = vis[i][k] = true;
}else{
vis[i][j] = vis[j][k] = vis[i][k] = true;
result++;
}
}
}
}
}
fout<<result;
return ;
}
最新文章
- MathType 6.9 介绍安装
- PADSPCB权威指南-第一章 PADS软件系统(部分)(原创)
- JAVA对象转化JSON出现死循环问题
- DiskGenius无损调整分区大小
- 深入研究java.lang.ThreadLocal类(转)
- U盘启动
- BZOJ 4503 两个串(FFT)
- Linux Shell 函数返回值
- weka对数据进行预测
- C#编程语言之委托与事件(二)—— C#事件
- MSSQL死锁进程查看及关闭
- Paper | 亚像素运动补偿 + 视频超分辨
- 流计算技术实战 - CEP
- C:基础知识
- 客户端负载均衡Feign之一:申明式服务调用Feign入门示例
- cxRichEdit1获取EXCEL的区域图片
- e606. Determining Which Component or Window Has the Focus
- DAO层注入HibernateTemplate的两种方式
- java数据结构之递归算法
- Python中numpy.apply_along_axis()函数的用法