-
[BOJ] 다각형의 면적
BOJ2166 다각형의 면적 꼭짓점 중 하나를 기준점으로 잡고, 모든 연속한 점쌍에 대해 외적을 구한 후 합하면 됩니다. 외적의 총합이 음수일 수도 있기 때문에 절댓값을 반드시 취해줘야합니다. #include<bits/stdc++.h> using namespace std; using ll=long long; using dot=pair<ll,ll>; dot operator-(dot a,dot b){ return {a.first-b.first,a.second-b.second}; } ll ccw(dot a,dot b,dot c){ dot x=b-a,y=c-a; return x.first*y.second-x.second*y.first; } int main(void){ ios::sync_with_stdio(0);cin.tie(0); int n; cin>>n; vector<dot> v(n); dot f; ll sum=0; for(int i=0;i<n;i++){ cin>>v[i].first>>v[i].second; if(i){ sum+=ccw(f,v[i-1],v[i]); } else{ f=v[i]; } } sum=abs(sum);...
-
[BOJ] 복도 뚫기
BOJ9373 복도 뚫기 센서와 벽을 노드 취급하고, 간선은 두 노드 사이에 들어갈 수 있는 원의 최대 지름으로 합시다. $O(N^2)$번의 연산이 요구되므로 N<=1,000인 이 문제에서는 무리없이 해결 가능합니다. 이 때, 경로가 존재하지 않을 때까지 두 노드 사이를 차단한다고 생각해봅시다. 경로가 하나라도 존재할 때 차단되지 않은 간선의 가중치 최솟값이 그 때 존재하는 경로만을 고려할 때의 답이라고 할 수 있습니다. 그렇다면 이런 가중치의 최솟값을 최대화하면 되는데, 이는 간선을 가중치 기준으로 정렬하고 가중치가 작은 것부터 차단해가며 완전히 모든 경로가...
-
[BOJ] 풍선
BOJ4716 풍선 그리디라는 깔끔하고 우아한 풀이가 있으나 실상은 팀노트가 있는 MCMF를 활용하여 짜는 것이 정신적 스트레스를 덜 받습니다. MCMF로 푸는 경우 노드는 SOURCE / SINK 각 팀 방 A, B 로 설정하고 간선의 가중치와 용량을 적절히 설정해주면 됩니다. 단, MCMF로 풀 때에는 일반적으로 사용하는 느린 MCMF로는 TLE를 받게 되며 커팅을 추가하거나 헬조선 MCMF를 사용하여야 AC를 받을 수 있습니다. #include<bits/stdc++.h> using namespace std; using pi=pair<int,int>; const int MAXN=1010; //Hell-Joseon MCMF struct edg{ int pos, cap, rev,...
-
[BOJ] A+B
BOJ1000 A+B 가장 기초적인 문제입니다. //C #include<stdio.h> int main(void){ int a,b; scanf("%d%d",&a,&b); printf("%d",a+b); } #Python a,b=map(int,input()) print(a+b)