几何+map套set——cf1163C
2024-09-06 10:23:24
能灵活用map+set的组合就能过这题了
/*
分成三个步骤来做:
1.通过点两两构造线
by=ax+c,先求a,b,再求c,用gcd(d,b)简化
2.线去重:用map+pair
3.统计交点
*/
#include<bits/stdc++.h>
#include<map>
using namespace std;
#define ll long long
#define maxn 2005
map<pair<int,int>,set<int> > mp;
map<pair<int,int>,set<int> >::iterator it;
struct Node{int x,y;}p[maxn]; int main(){
ll n,ans=,lines=;cin>>n;
for(int i=;i<=n;i++)cin>>p[i].x>>p[i].y;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++){
int a=p[i].y-p[j].y,b=p[i].x-p[j].x;
int d=__gcd(a,b);
a/=d,b/=d;
if(a< || a==&&b<){b*=-;a*=-;}
int c=(ll)b*p[i].y-(ll)a*p[i].x;
pair<int,int> p=make_pair(a,b);
if(mp[p].find(c)==mp[p].end()){
++lines;
mp[p].insert(c);
ans+=(ll)lines-mp[p].size();//所有已经存在的线-平行的线
}
}
cout<<ans<<endl;
}
最新文章
- 合并两个java bean对象非空属性(泛型)
- jQuery Mobile 工具栏
- HoloLens开发手记 - Unity之Spatial mapping 空间映射
- UVA11584 划分成回文串
- linux kill信号列表
- kindeditor编辑器
- 【JS】Intermediate6:jQuery
- AI自动寻路
- CF 579A Raising Bacteria
- web学习:Spring2.5+Hibernate3.3+Struts1.3整合小例子
- partial类修饰符
- 查看AIX是32位还是64位,查看内存、cpu等参数
- iPhone与iWatch连接、控制、数据传递(Swift)
- WPF的消息机制(二)- WPF内部的5个窗口之隐藏消息窗口
- 第四篇:Web框架 - Django
- java设计模式---三种工厂模式之间的区别
- Ubuntu 16.10的root默认密码设置
- [JavaScript] 邮箱验证
- 针对django2.2报错:UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode byte 0xa6 in position 9737: ill....
- [转] 深入理解React 组件状态(State)